6 An LP-relaxation of the 0-1 Program (examp-ip01r)

Run LPL Code  ,  PDF Document

Problem

This model is the same as the model examp-ip01 with the important difference that the variables are continuous and bounded by the interval [0..1]. Hence, this model is a LP program with continuous variable. It is called the LP relaxation of the corresponding 0-1 integer program.

A compact formulation using matrix notation for the model is:

min        c ⋅ x
subjectto  A ⋅ x ≥ b

           0 ≤ x ≤ 1

With the same data as in model examp-ip01, we get the following model:

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
           0 ≤ xj ≤ 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, and finally the constraints R and the minimizing objective function obj. Note that the only difference between this model and the model examp-ip01 is the variable declaration. The keyword binary has been removed and a lower and upper bound value for the variable [0..1] has been added.

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.)


Listing 4: The Complete Model implemented in LPL [10]
model Ip15_01r "An LP-relaxation of the 0-1 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))); 
            X{j}   := [0 0 0 0 0 1 1 1 0 0 0 0 1 1 1]; 
                 // X = 0-1 solution of the examp-ip01.lpl model 
  variable  x{j} [0..1]; 
  constraint R{i} : sum{j} A*x >= b; 
    --ADDED_a1: x[11]+x[14] >= 1; //add constraints 
    --ADDED_a2: x[9] +x[14] >= 1; 
    --ADDED_b1: x[13]+x[11] >= 1; 
    --ADDED_b2: x[8] +x[11] >= 1; 
    --ADDED_c:  x[6]  = 1; 
    --ADDED_d:  x[7]  = 1; 
    --ADDED_e:  x[15] = 1; 
  minimize obj    : sum{j} c*x; 
  Write('The optimal solution is as follows:' n 
Obj value = %8.4f , %9d , %9d 
rounded true 0-1 value' n', 
         obj, sum{j} c*Round(x), sum{j} c*X); 
  Write{j}(' x(%2s) = %8.4f %5d %10d' n', j,x,Round(x),X); 
end

Solution

The model has the following solution:

    (  0   0  0   0    0 0.16  1  1  1  0)
x =
     0.14  0  0  0.04  1

The optimal value of the objective function is:

obj = 201.52

In the following listing, we compare the three solutions: (1) the LP relaxation, (2) the rounded solution of the LP relaxation, and (3) the 0-1-IP solution. The LP relaxation has the optimal solution of 201.5179, the rounded problem has a solution of 181, which is far away from the true 0-1 solution which is 255. The rounded solution has no merit for the true integer solution.

  Obj value = 201.5179 ,     181 ,       255 
 
                           rounded    true 0-1 value 
         x( 1) =   0.0000     0           0 
         x( 2) =   0.0000     0           0 
         x( 3) =   0.0000     0           0 
         x( 4) =   0.0000     0           0 
         x( 5) =   0.0000     0           0 
         x( 6) =   0.1563     0           1 
         x( 7) =   1.0000     1           1 
         x( 8) =   1.0000     1           1 
         x( 9) =   1.0000     1           0 
         x(10) =   0.0000     0           0 
         x(11) =   0.1429     0           0 
         x(12) =   0.0000     0           0 
         x(13) =   0.0000     0           1 
         x(14) =   0.0435     0           1 
         x(15) =   1.0000     1           1

In contrast to the rounded version, the LP relaxation has an important function for the integer problem: The LP relaxation generates a lower bound for the integer solution. By solving the LP relaxation, we know that the optimal value of the integer problem cannot be below the optimal value of the LP relaxation. In our model, the optimal solution of the integer problem must be at least 201.5179 (we know already that it is 255). This is an important fact.

But we may say more about the relation between the LP relaxation and the 0-1-IP problem. For example, we can look at a particular inequality. Let’s choose just an arbitrary one, say:

52x9 +  14x11 + 92x14 ≥ 58

What can we say about that particular inequality? If x14 is zero then both x9 and x11 must be one. Why? Because if x14 = 0, then the inequality reduces to:

52x9 +  14x11 ≥ 58

However, this can only be the case if – in the 0-1 integer problem – both x9 and x11 are 1. Hence, we can add the two following inequalities to the LP relaxation model:

x14 + x9 ≥ 1  ,   x14 + x11 ≥ 1

Why? These two additional constraints do not violate the 0-1-IP solution: if x14 = 1 then both inequalities are fulfilled, if x14 = 0 then both x9 and x11 must be 1. That is exactly what the initial inequality claims if the values must be 0 or 1.

Now we solve the problem again without excluding a feasible solution of the 0-1 IP problem. What is interesting now: After having added these two constraints to the LP relaxation and solving it again, the optimal solution will be 220.2321. It has increased considerably, and again we can say that this is a lower bound for the 0-1 integer problem.

In the same way we could now look at the inquality:

30x8 +  98x11 + 19x13 ≥ 44

and we can repeat the same idea: If x11 = 0 then both x8 and x13 must be 1 in the integer program. This gives rise to the additional inequalities:

x11 + x8 ≥ 1  ,   x11 + x13 ≥ 1

Adding them too to the LP relaxation and solving the problem in R15, gives a optimal solution of 237.3750. That again rises the lower bound for the integer program considerably.

Looking at the solution, the unique value that is not integer is x6 = 0.1563. In the integer problem, x6 must be 0 or 1. So let try to set x6 = 0 and add this to the previous problem. Solving the problem results in an infeasible problem. Hence, there is no integer solution where x6 = 0. So let’s try x6 = 1 instead. We add this inequality to the previous problem. The new optimal solution is 243.8182.

Again, in the new solution we see that x7 = 0.5091, the unique value that is not integer. Hence, we try the same procedure again: setting first x7 = 0 and solving produces also an infeasible solution, setting x7 = 1, gives an optimal solution of 249.7778.

There is still one variable that is not integer: x15 = 0.8889. Adding x15 = 0 gives an infeasible solution, but setting x15 = 1 produces an integer solution with the optimum of 255. This is identical to the 0-1-IP problem and we have found the optimal solution to the 0-1-IP problem by adding appropriate inequalities (and equalities) to the LP relaxation. In our case, we added 4 inequalities and three equalities (by setting three variables to 1) (see the commented lines --ADDED... in the LPL code).

We conclude that the LP relaxation is important for the integer solution. It is the starting point of an iterative procedure that adds “valid” inequalities for the integer problem, until eventually we reach the optimal point of the integer problem. (Unfortunately, it is normally not so easy to add valid inequalities.) At least we have sketched an interesting idea on how to attack the solution of integer problems, that has great practical importance. For a more systematic approach to integer programming, see the interesting book [5]. See also two other small example in this context: alterna and unimodular.