minimize c^{T}x

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.

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^{T}x

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

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_{1} and T_{2}, add one edge between a node in
T_{1} and one node in T_{1} 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_{1} be a graph with a distinguished
node u and G_{2} be a graph with a distinguished node v. Consider the
composition operation on the graphs G_{1} and G_{2}
that merges u with v, resulting in a
single graph G. If A_{1} x >= b_{1} and
A_{2} y >= b_{2} were the convex hulls of the stable sets
of G_{1} and G_{2} respectively, then it can be shown that
A_{1} x >= b_{1}, A_{2} y >= b_{2},
x_{u} = y_{v} is the convex hull of the stable sets of G.

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}^{3}

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.

- 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, wis 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 subproblemsP1

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}^{3}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}^{3}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}^{3}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}^{3} - 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.

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

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