wiki:CglLiftAndProject

CglLiftAndProject

Contributor: Robin Lougee-Heimer
Maintainer: Robin Lougee-Heimer, robinlh@…

Introduction

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. 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 {cx: A x >= 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.


Notes

  1. Not a general purpose cut generator.
  1. Numerically unstable.

Papers, Presentations, and 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, (1993) 295-324.
    • This was the reference used for the implementation.

Documentation and Bug Reports

See the section "Project Links" on the Cgl main Trac page.

Last modified 12 years ago Last modified on Nov 18, 2006 12:27:37 PM