Reduce-and-Split Cuts: Improving the Performance of Mixed-Integer Gomory Cuts

Kent Andersen (), Gérard Cornuéjols () and Yanjun Li ()
Additional contact information
Kent Andersen: CORE, Université Catholique de Louvain, 1348 Louvain-la-Neuve, Belgium
Gérard Cornuéjols: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, and LIF, Faculté des Sciences de Luminy, 13288 Marseille, France
Yanjun Li: Krannert School of Management, Purdue University, West Lafayette, Indiana 47907

Management Science, 2005, vol. 51, issue 11, 1720-1732

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.

Keywords: integer programming; mixed-integer programming; cutting plane; split cut; mixed-integer Gomory cut; reduce-and-split cut (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.1050.0382 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:51:y:2005:i:11:p:1720-1732

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().