Problem
The general linear 01 integer programming model – called 01IP – consists of a linear objective function f(x), m linear constraints g_{i}(x), and n 0  1 integer variables. It can be compactly formulated as follows (see [11]):
A more compact formulation using matrix notation for the model is:
The objective function f the constraints g_{i}, and X (in the general model format) are as follows:
The 01IP 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 01IP model is also difficult to solve in general. (To get an idea solve the following model: lp2000. Then try to solve ip012000.)
In the following a problem with random data is specified (with n = 15 and m = 15):


The data given above specify the following explicit linear program:
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.
model Ip1501 "A 01 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 :

The optimal value of the objective function is:

Comparing the optimal solution of the three problems (1) examplp, (2) exampip, and (3) this one, we have the following optimal values: 174.8096 for the LP, 201 for the IP and 255 for the 01IP model.
Do the increasing optimal values for LP, IP and 01IP 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 01IP optimum compared with the IP optimum.
One may take the bait to solve the 01IP problem using the following procedure :
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 01 integer problem.)
All solution values for x are in the interval [0…1].
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 01 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 01IP problem, see some explanation in the model example exampip01r.
Further Comments
There is a surprisingly rich application field for 01integer programming, as there is for integer programming in general. 01 integer programming is used in the following context:
To model problems with logical conditions, Boolean constraints or expressing some kind of “dichotomy”.
To model combinatorial problems, such as sequencing problems and others.
To model nonlinear problems. They can often be translated into 01 integer (linear) problems.
For a short guide to 01 integer model formulation and how logical conditions can be integrated into a mathematical model see the paper [8].