Introduction to Integer Linear Programming

1. Introduction

A Linear Programming (LP) problem is of the form

minimize c^Tx
subject to
A x >= b

where A (a rational mxn matrix), c (a rational n-vector) and b (a rational m-vector) are given and x is an n-vector to be determined. In other words, we try to find the minimum of a linear function over a feasible set defined by a finite number of linear constraints. It can be shown that a problem with linear equalities or "<=" linear inequalities can always be put in the above form, implying that this formulation is more general than it might look. An Integer Linear Programming (ILP) problem is obtained from an LP problem by requiring that all entries of the solution vector x are integer. LP problems are "easy" to solve (they are in the complexity class P), whereas ILP problems are, in general, difficult (they are NP-hard).

If we assume that the set Q = {x | A x >= b} is nonempty and bounded, one of the vertices of Q is an optimal solution to the LP. This is not the case for an ILP problem, where the optimal solution may lie in the interior of Q. However, if Q' = {x | A' x >= b'} is the convex hull of the integer points in Q (a.k.a. the integer hull of Q), then an optimal solution of the ILP may be found by solving an LP problem over Q'. The ability to find the integer hull Q' of a given set Q allows us to transform a "hard" problem into an "easy" one.

Two main research directions present themselves: First, the study of the integer hull of the solutions for a particular problem. Its ultimate goal, is to find a linear description of the corresponding integer hull. The second one, more applied, is the study of techniques for finding the optimal solution of a given ILP problem. Here Branch-and-Bound and Branch-and-Cut are the methods of choice.

General references:

Bertsimas D., Tsitsiklis J.N. (1997), Introduction to Linear Optimization, Athena Scientific Series in Optimization and Neural Computation.
Nemhauser G.L., Wolsey L.A. (1988), Integer and Combinatorial Optimization, Wiley.
Schrijver A. (1986), Theory of Linear and Integer Programming, Wiley.
Wolsey L.A. (1998) Integer Programming, Wiley.

2. Integer Hulls

It can be shown that the integer hull of any polyhedron Q = {x | A x >= b} is defined by a finite set of linear inequalities. When the integer hull is full dimensional, there is a set of inequalities that is required in its linear description. These inequalities are called facet defining inequalities of the integer hull. The study of these inequalities for particular ILP problems is an important area of research with practical implications (see the next section).

As an illustration, consider the following graph problem: A set S of nodes in a graph G = (V, E) such that no two nodes in S are adjacent is called a stable set. For all v in V, let c_v be a cost (positive or negative) to be paid if node v is selected. The stable set problem asks for the stable set with minimum cost in G. To formulate this problem as an ILP, we can associate a variable x_v to each node v in V and write the problem as

minimize c^Tx
subject to
x_v+x_w <= 1 for each edge (v, w) in E (I)
0 <= x_v <= 1 for all v in V (II)
x_v in {0, 1} for all v in V. (III)

There is a natural bijection between the stable sets of G and the feasible {0, 1} vectors x for the above ILP: If node v is in set S, then x^S_v = 1, otherwise x^S_v = 0. The vector x^S is the characteristic vector of the set S. In the remainder, a "stable set S of G" will refer either to the node set S or its characteristic vector x^S.

Given a graph G, we are interested in getting the convex hull of the stable sets of G, i.e. a complete linear characterization of the convex hull. Unfortunately, unless G has certain properties, we do not know how to describe it completely. This motivates the study of facet defining inequalities that can be used on general graphs and the study of families of graphs for which a complete linear characterization can be found.

You can check that if G is not a bipartite graph then the feasible set bounded by inequalities (I) and (II) above has fractional vertices. For example, if G is a triangle, the point (0.5, 0.5, 0.5) is an extreme fractional point. Hence, if we want to describe the integer hull of the stable sets, we need additional constraints. These constraints should be satisfied by all feasible integer points, i.e. they should be valid for the integer hull.

An example of valid inequality is the following: if the nodes u, v, ..., z induce a complete graph of size k in G, then the inequality

x_u + x_v + ... + x_z <= 1 (IV)

is valid for all stable sets. Moreover, it can be shown that it is a facet defining inequality of the integer hull. If G is a triangle on the nodes u, v and w, adding the inequality x_u+x_v+x_w <= 1 to (I) and (II) yield the integer hull.

An example of family of graphs for which the inequalities (I) and (II) give the convex hull of the stable sets is the bipartite graphs. For perfect graphs, inequalities (I), (II) and (IV) describe this convex hull. When looking for families of graphs for which a complete linear characterization can be found, a possibility is to look at graphs defined by composition: A family F of graphs definable by compositions is defined by a finite set of elementary graphs in F and a finite set of operations that, given two (or more) graphs in F, produce a new graph in F. A simple example of such families of graphs is the trees (elementary graph: a single node; operation: Given two trees T₁ and T₂, add one edge between a node in T₁ and one node in T₁ to get a new tree T).

Provided that each composition operations in the definition of the family can be "translated" into operations on the system of linear inequalities, it is then easy to obtain the complete linear characterization on any graph of the family. A simple example is: Let G₁ be a graph with a distinguished node u and G₂ be a graph with a distinguished node v. Consider the composition operation on the graphs G₁ and G₂ that merges u with v, resulting in a single graph G. If A₁ x >= b₁ and A₂ y >= b₂ were the convex hulls of the stable sets of G₁ and G₂ respectively, then it can be shown that A₁ x >= b₁, A₂ y >= b₂, x_u = y_v is the convex hull of the stable sets of G.

3. Branch-and-Bound, Branch-and-Cut

Once a problem is set up as an ILP, the obvious question is "How do I solve this ?". One possibility is to enumerate all possible solutions, although this is feasible only for very small problems. The usual techniques used to solve ILP problems are Branch-and-Bound or Branch-and-Cut algorithms. They are both implicit enumeration techniques, implicit meaning that (hopefully) many solution will be skipped during enumeration as they are known to be non optimal.

As an illustration, consider the stable set problem (described in the previous section) on a triangle with nodes u, v and w, with cost vector c^T = (-2, -3, -4). In other words, we want to solve the ILP:

minimize (-2, -3, -4) x
subject to
x_u+x_v <= 1
x_u+x_w <= 1
x_v+x_w <= 1
x in {0, 1}³

Let us start with Branch-and-Bound (B&B). As its name indicates, two components are essential: Branching and Bounding.

The Branching is the simple operation that divides a problem into two (or more) subproblems such that the solution of the original problem can be found from the solutions of the subproblems. For the above ILP, a simple Branching operation is to pick a variable x_i and to replace the current problem by two subproblems. Both subproblems will be copies of the current problem with the variable x_i set to 0 in one of them and set to 1 in the other. Since the variable x_i has to take either value 0 or 1 in an optimal solution, this branching scheme guarantees that an optimal solution of the original problem will be an optimal solution of one of the two subproblems.
The Bounding operation is a function that returns a bound on the optimal solution of the current subproblem. (For a minimization problem, the returned value will be a number L smaller or equal to the value of an optimal solution). For ILP problems, a natural choice is to remove the integrality constraints on the variables (possibly replacing them by lower and upper bounds on the variables), transforming the subproblem to an LP problem, called the LP relaxation of the subproblem, easy to solve to optimality. Since the feasible solutions of the ILP subproblem are all feasible for the LP problem, the optimal solution of the former will always be worse or equal to the optimal solution of the latter. An additional use of the bound obtained is that it is possible to discard subproblems that have a bound L worse than the value Z of the best currently known solution of the original problem: Indeed, the bound tells us that the optimal solution of the subproblem cannot be better than L and we already know that the optimal solution of the original problem has a value Z or better. It follows that the optimal solution of the subproblem is of no use to us and we can fathom the subproblem without solving it.

Using these branching and bounding procedures on the above example produces the following:

Bounding of the starting problem: The optimal solution to the corresponding LP:
minimize (-2, -3, -4) x
subject to
x_u+x_v <= 1
x_u+x_w <= 1
x_v+x_w <= 1
0 <= x_i <= 1 for all i=u, v, w
is x^T = (0.5, 0.5, 0.5) with a value of -4.5. (The optimal value of the ILP is, of course x^T = (0, 0, 1) with value -4).

Branching: Let us pick variable x_u and create the two subproblems

P1
minimize (-2, -3, -4) x
subject to
x_u+x_v <= 1
x_u+x_w <= 1
x_v+x_w <= 1
x_u = 0
x in {0, 1}³ and P2
minimize (-2, -3, -4) x
subject to
x_u+x_v <= 1
x_u+x_w <= 1
x_v+x_w <= 1
x_u = 1
x in {0, 1}³

After simplifications, we obtain

P1
minimize -3 x_v - 4 x_w
subject to
x_v <= 1
x_w <= 1
x_v+x_w <= 1
x_u = 0
x in {0, 1}³ and P2
minimize -2 -3 x_v - 4 x_w
subject to
x_v <= 0
x_w <= 0
x_v+x_w <= 1
x_u = 1
x in {0, 1}³

Looking at subproblem P1, the bounding procedure returns the solution x^T = (0, 0, 1) with a value of -4. Since this solution is integral, it is the optimal solution of P1 and x is a feasible solution to the original problem with value Z = -4.
Looking now at problem P2, the bounding procedure returns the solution x^T = (1, 0, 0) with a value of -2. Since this bound is worse (i.e larger, for a minimization problem) than the current value Z=-4, we can fathom the subproblem without further consideration.
Since all subproblems have been solved or fathomed, we now have the optimal solution to the original problem: x^T = (0, 0, 1) with value -4.

Let us now turn to Branch-and-Cut. This is essentially a Branch-and-Bound as described above with an additional Cutting step. The idea is to generate valid inequalities for the integer hull of the current subproblem and add them to the linear description of the subproblem and its descendants. The motivations for adding this Cutting step are essentially that adding cuts might

improve the value returned by the bounding procedure and allow the fathoming of subproblems without resorting to Branching.
help in producing an integer solution for the LP relaxation of the subproblem and thus terminates its analysis.

Cut generations procedure are either problem dependent or generic (i.e. applicable to any ILP, or 0-1 ILP problems). Problem dependent procedures usually are related to facets defining inequalities of the integer hull of the problem at hand. Examples of generic procedures are the Gomory Cuts for general ILP problems or Lift-and-Project cuts for 0-1 ILP problems.

Additional informations:

Balas E., Ceria S., Cornuejols G., "A lift-and-project cutting plane algorithm for mixed 0-1 programs", Mathematical Programming, 58 (1993), 295-324.
Balas E., Ceria S., Cornuejols G., Natraj N.R., "Gomory Cuts Revisited", OR Letters, 19 (1996), 1-9.
Padberg, M., Rinaldi, G., "A branch-and-cut algorithm for the solution of large-scale traveling salesmen problems", SIAM Review 33 (1991), 1-41.

Back to main page