4 A Integer Linear Program (examp-ip)

Run LPL Code  ,  PDF Document

Problem

The general linear integer programming model – called IP – contains a linear objective function f(x), m linear constraints gi(x), and n integer variables. It can be compactly formulated as follows (see [11]):

           ∑
min             cjxj
           j∑∈J
subjectto       ai,jxj ≥ bi                         forall i ∈ I
           j∈J
                  +
           xj ∈ ℕ                                  forall j ∈ J
           I = {1 ...m }, J = {1 ...n}, m, n ≥ 0

A more compact formulation using matrix notation for the model is :

min        c ⋅ x
subjectto  A ⋅ x ≥ b
                 +
           x ∈ N

The objective function f, the constraints gi, and x (in the general model format) are as follows:

f(x1,...,xn) =   c1x1 + ...+ cnxn
gi(x1,...,xn ) =  bi - (ai,1x1 + ...+ ai,nxn) ≤ 0   forall i = 1,...,m
                 x ∈ Nn

The IP model has the same notation as the LP model, the only difference is that the variables are integer values. However, IP model are much more difficult to solve in general. (To get an idea solve the following model: lp2000. Then try to solve ip2000.)

In the following a problem with random data is specified (with n = 15 and m = 15):

    (                                                          )
c =  16  73  39  81  68  60  90  11  33  89  71  12  24  23  47

    (                                                           )         (    )
    | 87  34  0   0   43  0   52  85  36  0   0   0   0   0   0 |         |  0 |
    | 0   0   39  0   84  0   0   88  0   0   0   0   0   0   22|         |  0 |
    || 55  63  79  0   0   0   0   71  0   0   0   0   70  0   79||         ||  0 ||
    || 0   0   0   0   0   0   0   73  0   0   0   22  0   0   0 ||         ||  0 ||
    || 0   0   0   66  0   0   34  0   0   24  0   61  0   0   64||         ||  0 ||
    || 0   0   16  19  0   0   0   0   0   0   0   0   0   0   18||         ||  0 ||
    || 15  70  61  0   0   0   0   0   0   0   0   0   0   0   0 ||         ||  0 ||
    |                                                           |         |    |
A = || 0   0   0   0   0   0   0   0   52  0   14  0   0   92  0 ||     b = || 58 ||
    || 0   0   0   0   0   0   0   30  0   0   98  0   19  0   0 ||         || 44 ||
    || 0   70  37  0   0   0   0   0   0   0   0   86  0   93  0 ||         ||  0 ||
    || 90  0   82  0   66  0   0   0   0   26  0   0   0   0   0 ||         ||  0 ||
    | 77  30  0   0   0   0   13  10  0   0   0   50  0   0   0 |         |  0 |
    || 0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 ||         ||  0 ||
    |( 0   72  0   0   0   79  0   0   0   0   0   11  90  0   0 |)         |(  0 |)
      0   0   0   0   0   32  55  0   23  0   0   0   0   0   36            119

The data given above specify the following explicit linear program:

min        16x1 + 73x2 + 39x3 + 81x4 + 68x5 +  60x6 + 90x7 + 11x8 + 33x9
               +89x10  + 71x11 + 12x12 + 24x13 + 23x14 + 47x15
subjectto  87x1 + 34x2 + 43x5 + 52x7 + 85x8 +  36x9 ≥ 0
           39x3 + 84x5 + 88x8 + 22x15 ≥  0
           55x  + 63x  + 79x  + 71x  + 70x   + 79x   ≥  0
              1      2       3      8      13      15
           73x8 + 22x12 ≥ 0
           66x4 + 34x7 + 24x10 + 61x12 + 64x15 ≥ 0
           16x3 + 19x4 + 18x15 ≥ 0
           15x1 + 70x2 + 61x3 ≥  0

           52x9 + 14x11 + 92x14 ≥ 58
           30x8 + 98x11 + 19x13 ≥ 44
           70x2 + 37x3 + 86x12 + 93x14 ≥ 0
           90x1 + 82x3 + 66x5 + 26x10 ≥  0
           77x  + 30x  + 13x  + 10x  + 50x   ≥  0
              1      2       7      8      12
           72x2 + 79x6 + 11x12 + 90x13 ≥ 0
           32x6 + 55x7 + 23x9 + 36x15 ≥  119
           xj ∈ N+    forall j ∈ {1...15 }

Modeling Steps

The formulation of the model in LPL modeling language is straightforward and the notation is close to the mathematical notation using indices: First we define the two sets i and j. Then we declare and assign the data as parameters A, c, and b. The variable vector x is declared with the keyword integer (the only difference to the LP model), and finally the constraints R and the minimizing objective function obj are written.

Note that the data matrices A, b, and c are generated using LPL’s own random generator. (To generate the same data each time, the code can also use the function SetRandomSeed(a) where a is an integer.)


Listing 2: The Complete Model implemented in LPL [10]
model Ip15 "A Integer Linear Program"; 
  set i := [1..15];  j := [1..15]; 
  parameter A{i,j} := Trunc(if(Rnd(0,1)<0.25, Rnd(10,100))); 
            c{j}   := Trunc(Rnd(10,100)); 
            b{i}   := Trunc(if(Rnd(0,1)<0.15, Rnd(0,120))); 
  integer variable  x{j}; 
  constraint R{i} : sum{j} A*x >= b; 
  minimize obj    : sum{j} c*x; 
  Writep(obj,x); 
end

Solution

The small model defined above has the following solution :

    (                                          )
x =  0  0  0  0  0  0  0  2  4  0 0  0  0  0  1

The optimal value of the objective function is:

obj = 201

If we compare this solution with the corresponding LP model in examp-lp, we notice that the objective value is much larger (201 compared to 174.8096). Furthermore, the vector x is not simply the “round-down” of the LP solution, as one may expect. To understand why we cannot simply round up or down to get an integer solution from a corresponding LP model, open the model willi155 and read the modeling text to understand why.

Further Comments

IP problems are much more difficult to solve than LP problems in general. However, there is a surprisingly rich application field for integer programs. Obvious applications are problems where we have indivisible objects, such as number of persons, machines, etc. However, these are not typical applications. If we have the number of drivers in a small company then we may model this as an integer quantity, however if we have the population in a country then we may approximate it as a continuous variable. This obvious aspect, however, does not reveal the real power of integer programming. We really need integer programming in the four following contexts in this order of importance from a practical point of view:

  1. To model problems with logical conditions. In this case, the integrality is even reduced to variables that only take the value 0 or 1 (see the next model examp-ip01) for more information about them and how to specify logical constraints).

  2. To model combinatorial problems, such as sequencing problems, (job-shop) scheduling, and many others. Many of them are again transformed to integer problems with 0 - 1 variables. A small example can be found here: knapsack.

  3. To model non-linear problems. There exist techniques that translate a non-linear problem into a integer (linear) problem. (For more information see, for example bill320).

  4. To model problems where we need discrete (integer) numbers for various entities. An example for this last category is given by the following problem: magics another is mobile1.

Various linear problems with a special structure (the matrix A must be uni-modular) such as the transportation problem have integer solutions without explicitly formulating them as integer programs. They can be solved as LP progams.

Models with general integer variables with an upper bound can also be transformed into models that only contain 0 - 1 integer variables. The transformation is as follows. Let x ∈{0, 1,,u} be an general upper (and lower) bounded integer variable. Then substitute the variable 0 x u by the expression:

                      r
δ0 + 2δ1 + 4δ2 + ...+ 2 δr

where δ0,r are 0 - 1 integer variables, and r is the smallest number, such that u 2r.

Furthermore, problems which contain general integer variables when modelling them in a straightforward way are sometimes preferably modeled with 0 - 1 variables. An example is the Sudoku game (see the puzzlebook that has plenty of such models).