Introduction to Integer Linear Programming

1. Introduction

A Linear Programming (LP) problem is of the form

minimize cTx
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:

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 cv 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 xv to each node v in V and write the problem as

minimize cTx
subject to
xv+xw <= 1     for each edge (v, w) in E    (I)
0 <= xv <= 1   for all v in V     (II)
xv 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 xSv = 1, otherwise xSv = 0. The vector xS 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 xS.

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

xu + xv + ... + xz <= 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 xu+xv+xw <= 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 T1 and T2, add one edge between a node in T1 and one node in T1 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 G1 be a graph with a distinguished node u and G2 be a graph with a distinguished node v. Consider the composition operation on the graphs G1 and G2 that merges u with v, resulting in a single graph G. If A1 x >= b1 and A2 y >= b2 were the convex hulls of the stable sets of G1 and G2 respectively, then it can be shown that A1 x >= b1, A2 y >= b2, xu = yv 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 cT = (-2, -3, -4). In other words, we want to solve the ILP:

minimize (-2, -3, -4) x
subject to
xu+xv <= 1
xu+xw <= 1
xv+xw <= 1
x in {0, 1}3

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

Using these branching and bounding procedures on the above example produces the following: 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 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:

Back to main page