Reduce-and-split cuts: Improving the performance of mixed-integer gomory cuts

Andersen, Kent;Cornuejols, Gérard;Li, Yanjun
(2005) Management science — Vol. 51, n° 11, p. 1720-1732 (2005)

Files

pdfdocument.pdf
  • Restricted Access
  • Adobe PDF
  • 2.44 MB
No access

Details

Authors
  • Andersen, KentUCLouvain
    Author
  • Cornuejols, Gérard
    Author
  • Li, Yanjun
    Author
Abstract
Mixed-integer Gomory cuts have become an integral part of state-of-the-art software for solving mixed-integer linear programming problems. Therefore, improvements in the performance of these cutting planes can be of great practical value. In this paper, we present a simple and fast heuristic for improving the coefficients on the continuous variables in the mixed-integer Gomory cuts. This is motivated by the fact that in a mixed-integer Gomory cut, the coefficient of an integer variable lies between 0 and 1, whereas for a continuous variable, there is no upper bound. The heuristic tries to reduce the coefficients of the continuous variables. We call the resulting cuts reduce-and-split cuts. We found that on several test problems, reduce-and-split cuts can substantially enhance the performance of a branch-and-bound algorithm.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Andersen, K., Cornuejols, G., & Li, Y. (2005). Reduce-and-split cuts: Improving the performance of mixed-integer gomory cuts. Management science, 51(11), 1720-1732. https://doi.org/10.1287/mnsc.1050.0382 (Original work published 2005)