An efficient Solution Method for Mixed Integer Programs
Download slides in PostScript format, PDF format, or PowerPoint
The topic of this talk is the solution of general mixed integer programs
using cutting planes derived from disjunctive formulations. Although the
theory applies to general integer programs, this talk is restricted to
0/1-programs, where the integer constrained variables can only take the
values 0 or 1.
The basic formulation of a 0/1-program is shown
in slide 2. In Branch-and-Bound the LP-relaxation
of that formulation, also shown in slide 2,
is typically used as a lower bound. The lift-and-project approach is a
method to find inequalities that are valid for the 0/1-program but are
violated at the optimal solution to the LP-relaxation. Hence adding these
inequalities to the LP-relaxation, tightens the formulation and thereby
strengthens the lower bounds in a Branch-and-Bound framework. The original
lift-and-project method is due to Egon Balas, Gerard Cornuéjols
and Sebastian Ceria .
Since each 0/1-variable xi
must take either the value 0 or 1, any feasible solution to the 0/1-program
must also satisfy the disjunction shown in slide
4. This disjunction should be read as, either a feasible solution
x must satisfy the left term or it must satisfy the right term.
Such a disjunction is a strengthening of the LP-relaxation if the variable
is fractional in the optimal solution to the LP-relaxation. What we seek
are inequalities valid for Pi, the
set of solutions x that satisfies the disjunction, but which are
violated at the optimal solution to the LP-relaxation.
Slides 5-13 illustrate
a three-dimensional example where a cutting plane is found, based on the
two term disjunction in slide 7, which separates
the optimal LP-relaxation solution from the set of feasible solutions to
In  Egon Balas describes how the convex
hull of the feasible solutions to a disjunctive program can be represented
using a higher dimensional linear formulation. In slide
15 the higher dimensional formulation representing Pi
is shown. Here x1 can be interpreted
as a feasible solution to the first term of the disjunction and likewise
x2 is a feasible solution
to the second term. The interpretation of this program is that an x
belongs to Pi if and only if it
can be written as a convex combination of an x1
satisfying the first term, and an x2
satisfying the second term. To get the valid inequalities for x
implied by this program, the higher dimensional variables x1
and x2 are projected out. In slide
14 is shown the corresponding projection cone.
A cut is valid for Pi if and only
if it is feasible in this linear program. Hence a valid inequality for
Pi and thereby the 0/1-program can
be obtained by optimizing a linear program similar, with an objective of
cutting off the LP relaxation solution (slide 16).
The problem with the linear program in slide 14
is that it describes a cone and is therefore unbounded (or zero). Interpreting
this linear program as the dual, the corresponding primal problem (slide
17) is then infeasible. The infeasibility comes from trying to describe
the LP-relaxation solution as a convex combination of solutions to the
two terms of the disjunction. Slide 18 illustrates
this infeasiblity. The solution is to normalize the cut generation linear
program by adding a constraint (or constraints) which bounds the cone.
This corresponds to relaxing the primal formulation to make it feasible.
In slide 19 is proposed one such normalization.
If the norm used in the dual is the (1+p)-norm then the corresponding
norm in the primal is the (1+1/p)-norm. The geometric interpretation
of this type of normalization is to introduce an extra point x*
inside the convex hull and then minimize the distance between x*
and the LP-relaxation solution, in the (1+1/p)-norm. This is illustrated
in slide 20.
An alternative normalization is to restrict the
multipliers (slide 21). The primal interpretation
of this is to relax all constraints by the same amount t. The geometrical
interpretation is to expand the feasible regions for each disjunctive term,
until the LP-relaxation solution lies within the convex hull of these relaxed
sets. This is illustrated in slide 22.
Slide 23 gives a look at the structure of
the cut generation linear program. This program is quite large compared
against the LP-relaxation and requires substantial effort to solve. One
of the key ideas that makes the lift-and-project method work in practice
is the observation that it is possible to ignore all variables that are
at a bound in the LP-relaxation solution (slide 24).
Thus the cut LP can be formulated and optimized in the subspace of the
fractional variables only. Using the solution from this subspace formulation
a full-space cut can easily be constructed. Since branching in Branch-and-Bound
is usually accomplished by fixing one variable to either 0 or 1, then in
the LP-relaxation solution, the fixed variables will be at a bound and
hence lifted. Therefore the subspace formulation will not contain any fixed
variables and the resulting cut can easily be made globally valid when
lifted to the full space.
Another idea towards reducing computational time is to include only
those original constraints tight at the LP-relaxation solution (slide
25). The resulting cuts might be weaker, but computational testing
in  indicates that the reduction in computational time is worth
In slide 26 is displayed
the resulting cut LP used along with the deleted rows and columns corresponding
to lifted variables and the deleted columns corresponding to ignored original
Multiple Cut Generation
Since each basic solution to the cut LP corresponds to a valid inequality
for the 0/1-program, several different cuts can be obtained by exploring
different basic solutions. One idea, shown in slide
27, is to force some of the multipliers currently basic in the cut
LP to be non-basic. This is accomplished by forcing them to zero. Reoptimizing
the cut LP will then yield a different basic solution which might result
in a different cut. An alternative approach suggested by Egon Balas 
is to do some pivots in the cut LP to reach alternative solutions.
A second idea to obtain alternative cuts (slide
28) is to find several solutions to the LP-relaxation and optimize
the cut LP with the objective of cutting off each of these solutions. These
extra LP-relaxation can be obtained by doing pivots in the LP-relaxation.
Slide 29 introduces the settings under which
the lift-and-project method was tested. The mentioned strong branching
is a feature of CPLEX which for each 0/1-variable computes the penalty
of forcing it to either zero or one. The penalty is computed by solving
the LP-relaxation with each variable fixed to either zero or one in turn,
within a fixed iteration limit. Strong branching is then used to determine
which fractional variables to use for cut generation. At most 50 fractional
variables are selected.
Slide 30 describes
how the lift-and-project cuts are used. Basically, a pool of cuts is generated
and added to the 0/1-program. The strengthened formulation is then given
over to either CPLEX 5.0 or XPRESS-MP to solve to completion. For cut generation,
the idea presented in slide 27 (fixing multipliers)
is used to generate multiple cuts from each cut LP. Not mentioned in the
talk, but in the paper , each cut is strengthened by exploiting
the integrality condition on other variables than the one used to build
the disjunction. The strengthening procedure is described in .
The following slides 31-35 presents the computational
results of the lift-and-project method compared against CPLEX 5.0. Here
C&B = Cut-and-Branch, where the 0/1-program is first strengthened
using lift-and-project cuts and the resulting program then solved by CPLEX
||E. Balas, Disjunctive Programming, Annals of Discrete Mathematics,
||E. Balas, Recent Advances in Lift-and-Project, Technical Report,
GSIA, Carnegie Mellon University (1997).
||E. Balas, S. Ceria, G. Cornuéjols, A lift-and-project cutting
plane algorithm for mixed 0-1 programs, Mathematical Programming, 58
||E. Balas, S. Ceria, G. Cornuéjols, Mixed 0-1 Programming
by Lift-and-Project in a Branch-and-Cut Framework, Management Science,
42 (1996) 1229-1246.
||E. Balas, R.G. Jeroslow, Strengthening cuts for mixed integer programs,
European Journal of Operational Research, 4 (1980) 224-234.
||S. Ceria, G. Pataki, Solving Integer and Disjunctive Programs by
Lift and Project, Proceedings of the 6th International IPCO Conference