# 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

algorithm.

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.

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

algorithm.

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.