Recent advances in lift and project

Monday, July 25, 2005 - 10:30am - 11:15am
EE/CS 3-180
Egon Balas (Carnegie-Mellon University)
In a recent joint paper with Michael Perregaard a
precise correspondence was established between lift-and-project
cuts for mixed 0-1 programs, simple disjunctive cuts
(intersection cuts) and mixed-integer Gomory cuts. The
correspondence maps members of one family onto members of the
others. It also establishes a many-to-one mapping between bases
of the higher-dimensional cut generating linear program (CGLP)
and bases of the linear programming relaxation of the given
mixed integer program. As a result, an algorithm is developed
that solves (CGLP) without explicitly constructing it, by
mimicking the pivoting steps of the higher dimensional (CGLP)
simplex tableau by certain pivoting steps in the lower
dimensional LP simplex tableau. Due to the smaller problem size
and the vastly reduced number of pivots needed by the new
algorithm, it finds a deepest lift-and-project cut typically in
a fraction of the time needed by the original (CGLP)-based

The new cut generating procedure can also be interpreted as an
algorithm for systematically strengthening mixed integer Gomory
(MIG) cuts. Starting with a MIG cut from a given source row k
of the optimal LP simplex tableau, a certain sequence of pivots
is performed, each of which results in a new simplex tableau,
generally neither primal nor dual feasible, such that the MIG
cut from the same source row k is guaranteed to be stronger (in
terms of the amount by which it cuts off the LP optimum) then
the previous MIG cut. In other words, if S is the set of all
bases (feasible or not) of the LP relaxation, this procedure
finds a member B of S such that the MIG cut from row k of the
simplex tableau associated with B is strongest over all bases
in S.

After extensive computational testing, the new procedure has
been incorporated in the MIP module of the commercial code
XPRESS, where it serves as the default cut generating routine.