Linear-programming-based lifting and its application to primal cutting-plane algorithms

Santanu S. Dey, Jean Philippe Richard

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


We propose an approximate lifting procedure for general integer programs. This lifting procedure uses information from multiple constraints of the problem formulation and can be used to strengthen formulations and cuts for mixed-integer programs. In particular, we demonstrate how it can be applied to improve Gomory's fractional cut, which is central to Glover's primal cutting-plane algorithm. We show that the resulting algorithm is finitely convergent. We also present numerical results that illustrate the computational benefits of the proposed lifting procedure.

Original languageEnglish (US)
Pages (from-to)137-150
Number of pages14
JournalINFORMS Journal on Computing
Issue number1
StatePublished - Jan 2009
Externally publishedYes


  • Integer programming
  • Primal cutting-plane algorithm


Dive into the research topics of 'Linear-programming-based lifting and its application to primal cutting-plane algorithms'. Together they form a unique fingerprint.

Cite this