Problem
The general linear integer programming model – called IP – contains a linear objective function f(x), m linear constraints g_{i}(x), and n 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 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):


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

The optimal value of the objective function is:

If we compare this solution with the corresponding LP model in examplp, we notice that the objective value is much larger (201 compared to 174.8096). Furthermore, the vector x is not simply the “rounddown” 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:
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 exampip01) for more information about them and how to specify logical constraints).
To model combinatorial problems, such as sequencing problems, (jobshop) 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.
To model nonlinear problems. There exist techniques that translate a nonlinear problem into a integer (linear) problem. (For more information see, for example bill320).
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 unimodular) 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:
where δ_{0},…,δ_{r} are 0  1 integer variables, and r is the smallest number, such that u ≤ 2^{r}.
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).