Reduce-and-split cuts: improving the performance of mixed-integer Gomory cuts

Reduce-and-split cuts: improving the performance of mixed-integer Gomory cuts

0.00 Avg rating0 Votes
Article ID: iaor2008970
Country: United States
Volume: 51
Issue: 11
Start Page Number: 1720
End Page Number: 1732
Publication Date: Nov 2005
Journal: Management Science
Authors: , ,
Keywords: cutting plane algorithms
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.

Reviews

Required fields are marked *. Your email address will not be published.