Linear-Programming-Based Lifting and Its Application to Primal Cutting-Plane Algorithms
(2009) INFORMS Journal on Computing — Vol. 21, n° 1, p. 137-150 (2009)
Files
No attached file found for this publication.
Details
- Authors
- 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.
- Affiliations
Citations
Dey, S. S., & Richard, J.-P. (2009). Linear-Programming-Based Lifting and Its Application to Primal Cutting-Plane Algorithms. INFORMS Journal on Computing, 21(1), 137-150. https://doi.org/10.1287/ijoc.1080.0284 (Original work published 2009)