Integer Programming

This full chapter is dedicated to integer programming.

The general linear programming model depends on the assumption of divisibility. In other words, the decision variables are allowed to take non-negative integer as well as fractional values. However, we quite often face situations where the planning models contain integer valued variables.

For instance, trucks in a fleet, generators in a powerhouse, pieces of equipment, investment alternatives and there are a myriad of other examples. In all such cases, an integer solution is desired, which can be easily obtained by rounding off the fractional values of the variables. But, rounding-off may result in sub-optimal or infeasible solutions. To overcome such difficulties, a different optimization model, which is referred to as integer programming has been developed.

Definitions: Integer Programming

The focus of this chapter is on solution techniques for integer programming models.

The mathematical model of the problem is as follows:

Optimize (maximize or minimize) c_jx_j

subject to
a_ijx_j ( ≤, =, ≥ ) b_i; i = 1, 2, ....., m

x_j ≥ 0; j = 1, 2, ....., n
x_j integer valued; j = 1, 2, ....., p ≤ n

If all the variables are restricted to take only integral values (i.e., p = n), the model is called a pure integer programming problem. To the contrary, if some variables are restricted to take only integer values, and the remaining are free to take any non-negative values, then it is called a mixed integer programming problem. When the decision variables are required to take value of either zero or one, it is called zero-one programming.

The mathematical model of zero-one programming is as follows:

Optimize (maximize or minimize) c_jx_j

subject to
a_ijx_j ( ≤, =, ≥ ) b_i; i = 1, 2, ....., m

x_j = 0 or 1; j = 1, 2, ....., n