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 x_t ≥ 0, -x_t ≥ -1 for x_t binary, explicitly stated in the constraint matrix.

Given canonical problem and the LP-relaxation solution, x, CglLiftAndProject attempts to construct a cut for every x_j such that 0 < x_j < 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.