Skip to content

CglLiftAndProject

Jump to bottom
Stefan Vigerske edited this page Mar 9, 2019 · 3 revisions

Contributor and Maintainer: Robin Lougee-Heimer

CglLiftAndProject is a very limited implementation of "Lift-and-Project" cuts.

The main purpose of this cut generator is to encourage someone to improve it (or better yet, to get them to CONTRIBUTE their own, better, implementation of lift-and-project cuts).

CglLiftAndProject is NOT a general purpose cut generators and is numerically unstable. It makes strong assumptions (i.e., the User knows if the requirments for this cg are satisfied). This implementation uses Normalization 1, and does not include lifting.

Assumes the mixed 0-1 problem min c'x such that Ax ≥ b is in canonical form with all bounds, including xt ≥ 0, -xt ≥ -1 for xt binary, explicitly stated in the constraint matrix.

Given canonical problem and the LP-relaxation solution, x, CglLiftAndProject attempts to construct a cut for every xj such that 0 < xj < 1.

References:

  • R. Lougee-Heimer, and M. Saltzman, "Implementing Lift & Project Cuts in the COIN-OR Cut Generator Library" presented at the INFORMS Annual Meeting, Miami, 2001.
  • Balas, Ceria, and Cornuejols, "A lift-and-project cutting plane algorithm for mixed 0-1 program", Math Prog 58, 295-324, 1993. This was the reference used for the implementation.
Clone this wiki locally