This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Dey, S. S. Articles by Richard, J.-P. Search for Related Content

Linear-Programming-Based Lifting and Its Application to Primal Cutting-Plane Algorithms

Center for Operations Research and Econometrics, Université Catholique de Louvain 34, B-1348 Louvain-la-Neuve, Belgium
School of Industrial Engineering, Purdue University, West Lafayette, Indiana 47907
santanu.dey{at}uclouvain.be
jprichar{at}ecn.purdue.edu

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.

Key words: integer programming; primal cutting-plane algorithm
History: received April 2006; revised December 2007; accepted April 2008.