Problem
This model is the same as the model exampip01 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 01 integer program.
A compact formulation using matrix notation for the model is:
With the same data as in model exampip01, we get the following model:
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 exampip01 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.)
model Ip15_01r "An LPrelaxation of the 01 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 = 01 solution of the exampip01.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 01 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:

The optimal value of the objective function is:

In the following listing, we compare the three solutions: (1) the LP relaxation, (2) the rounded solution of the LP relaxation, and (3) the 01IP 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 01 solution which is 255. The rounded solution has no merit for the true integer solution.
Obj value = 201.5179 , 181 , 255
rounded true 01 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 01IP problem. For example, we can look at a particular inequality. Let’s choose just an arbitrary one, say:
What can we say about that particular inequality? If x_{14} is zero then both x_{9} and x_{11} must be one. Why? Because if x_{14} = 0, then the inequality reduces to:
However, this can only be the case if – in the 01 integer problem – both x_{9} and x_{11} are 1. Hence, we can add the two following inequalities to the LP relaxation model:
Why? These two additional constraints do not violate the 01IP solution: if x_{14} = 1 then both inequalities are fulfilled, if x_{14} = 0 then both x_{9} and x_{11} 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 01 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 01 integer problem.
In the same way we could now look at the inquality:
and we can repeat the same idea: If x_{11} = 0 then both x_{8} and x_{13} must be 1 in the integer program. This gives rise to the additional inequalities:
Adding them too to the LP relaxation and solving the problem in R^{15}, 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 x_{6} = 0.1563. In the integer problem, x_{6} must be 0 or 1. So let try to set x_{6} = 0 and add this to the previous problem. Solving the problem results in an infeasible problem. Hence, there is no integer solution where x_{6} = 0. So let’s try x_{6} = 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 x_{7} = 0.5091, the unique value that is not integer. Hence, we try the same procedure again: setting first x_{7} = 0 and solving produces also an infeasible solution, setting x_{7} = 1, gives an optimal solution of 249.7778.
There is still one variable that is not integer: x_{15} = 0.8889. Adding x_{15} = 0 gives an infeasible solution, but setting x_{15} = 1 produces an integer solution with the optimum of 255. This is identical to the 01IP problem and we have found the optimal solution to the 01IP 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.