Columbia University

Download slides in PostScript format, PDF format, or PowerPoint format.

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

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 the 0/1-program.

In

An alternative normalization is to restrict the multipliers (slide 21). The primal interpretation of this is to relax all constraints by the same amount

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

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

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

The following slides 31-35 presents the computational results of the lift-and-project method compared against CPLEX 5.0. Here

[1] | E. Balas, Disjunctive Programming, Annals of Discrete Mathematics,
5(1979) 3-51. |

[2] | E. Balas, Recent Advances in Lift-and-Project, Technical Report,
GSIA, Carnegie Mellon University (1997). |

[3] | E. Balas, S. Ceria, G. Cornuéjols, A lift-and-project cutting
plane algorithm for mixed 0-1 programs, Mathematical Programming, 58
(1993) 295-324. |

[4] | 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. |

[5] | E. Balas, R.G. Jeroslow, Strengthening cuts for mixed integer programs,
European Journal of Operational Research, 4 (1980) 224-234. |

[6] | S. Ceria, G. Pataki, Solving Integer and Disjunctive Programs by
Lift and Project, Proceedings of the 6th International IPCO Conference
(1998) 271-283. |