We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Reduce-and-Split Cuts: Improving the Performance of Mixed-Integer Gomory Cuts.
- Authors
Andersen, Kent; Cornuéjols, Gérard; Yanjun Li
- Abstract
Mixed-integer Gomory cuts have become an integral part of state-of-the-art software for solving mixedinteger 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.
- Subjects
LINEAR programming; INTEGER programming; HEURISTIC programming; COMPUTER software; ALGORITHMS; BRANCH &; bound algorithms; MANAGEMENT; COMPUTERS in management
- Publication
Management Science, 2005, Vol 51, Issue 11, p1720
- ISSN
0025-1909
- Publication type
Article
- DOI
10.1287/mnsc.1050.0382