Integer Programming

Any integer linear program is defined by the number of variables and the number of constraints. As with linear programming, do not count the non-negativity restrictions as constraints. Almost any linear programming package assumes that unless told otherwise the variables must be non- negative. Please note that the mixed integer programming module can be used for integer programming, but not vice-versa.

Consider the following example:

maximize
subject to	350x1
x1
- x1
x1 , x2
x1 , x2	+ 500x2
+ 1.5x2
+ 4x2
>= 0
integer
<=
>=

15
0

The components and the data entry are exactly the same as for linear programming. (The difference is in the solution.)

Objective function. The choice of minimization or maximization is made in the usual way at the time of problem creation, but it can be changed on the data screen using the objective options above the data.

Objective function coefficients. The coefficients (typically referred to as cj ) are entered as numerical values.

Constraint coefficients. The main body of information contains the constraint coefficients, which typically are called the aijs . These coefficients may be positive or negative.

The constraint sign. This can be entered in one of two ways. It is permissible to press the [<] key, the [>] key, or the [=] key. When you go to a cell with the constraint sign, a drop-down arrow appears in the cell and can be used.

Right hand side coefficients. The values on the right hand side of the constraints are entered here. These are also termed the bis . They must be non-negative.

The solution

The solution is given by a simple screen with the variables and their values.

Iterations

The iterations can be found in another screen. The LP solution to the original problem (see iteration 1, level 0) had x1 and x2 both as nonintegers . We then branched on x1 by adding the constraint x1 <=10. The LP solution to this problem had x1 as an integer but x2 was noninteger , so we branched on x2 by adding the constraint ( x2 <=3). This yields an integer solution (iteration 3). We create the other branch by adding ( x2 >=4) and this yields an even better integer solution. We go back to the original node and create the branch x1>11 , which yields an infeasible solution. Therefore, we are done.

Graph

A graph is available for this module.