5 A 0-1 Integer Program (examp-ip01)

Run LPL Code  ,  PDF Document

Problem

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

           ∑
min             cjxj
           j∑∈J
subjectto       a  x ≥  b                          forall i ∈ I
                 i,j j    i
           j∈J
           xj ∈ {0,1}                              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 ∈ {0,1}

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 ∈ {0,1}

The 0-1-IP model has the same notation as the LP (and the IP) model, the only difference is that the variables are 0 - 1 integer values. The 0-1-IP model is also difficult to solve in general. (To get an idea solve the following model: lp2000. Then try to solve ip01-2000.)

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 ∈ [0,1 ]  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 binary (the only difference to the LP model), and finally the constraints R and the minimizing objective function obj.

Note that the data matrices A, b, and c are generated using LPL’s own random generator. (To generate each time the same data, the code can also use the function SetRandomSeed(a) where a is an integer.) Note also that only difference in the LPL formulation compared with the LP model is the word binary added to the variable declaration.


Listing 3: The Complete Model implemented in LPL [10]
model Ip1501 "A 0-1 Integer 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))); 
  binary 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  1  1  1  0  0 0  0  1  1  1

The optimal value of the objective function is:

obj = 255

Comparing the optimal solution of the three problems (1) examp-lp, (2) examp-ip, and (3) this one, we have the following optimal values: 174.8096 for the LP, 201 for the IP and 255 for the 0-1-IP model.

Do the increasing optimal values for LP, IP and 0-1-IP make sense? Of course, the IP model is “more” restricted, it only can have integer values, hence the IP optimal value can never be smaller than the LP optimal value. The same is true for the 0-1-IP optimum compared with the IP optimum.

One may take the bait to solve the 0-1-IP problem using the following procedure :

  1. Replace the requirement that the variables are 0 - 1 integer variables by the constraint 0 x 1, then solve this LP problem. (This LP problem is called the LP relaxation of the 0-1 integer problem.)

  2. All solution values for x are in the interval [01].

  3. Finally, round their values up to 1 or down to 0, depending of whether the value is closer to 1 or to 0.

Voilą! We can show with a tiny example (see willi155z), that this apparently reasonable approach is completely erroneous: while the LP relaxation of this tiny example has a feasible solution, the corresponding 0-1 problem is infeasible.

It seems difficult to derive the integer solution from the continuous LP problem. For a systematic procedure – called cutting plane method – that starts with the continuous LP problem to find an integer solution of the 0-1-IP problem, see some explanation in the model example examp-ip01r.

Further Comments

There is a surprisingly rich application field for 0-1-integer programming, as there is for integer programming in general. 0-1 integer programming is used in the following context:

  1. To model problems with logical conditions, Boolean constraints or expressing some kind of “dichotomy”.

  2. To model combinatorial problems, such as sequencing problems and others.

  3. To model non-linear problems. They can often be translated into 0-1 integer (linear) problems.

For a short guide to 0-1 integer model formulation and how logical conditions can be integrated into a mathematical model see the paper [8].