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

Santanu S. Dey, Jean Philippe Richard

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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
Volume21
Issue number1
DOIs
StatePublished - Jan 2009
Externally publishedYes

Keywords

  • Integer programming
  • Primal cutting-plane algorithm

Fingerprint

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