Strengthening Gomory Mixed-Integer Cuts: A Computational Study
Franz Wesselmann · 2009
Gomory mixed-integer cuts are an important ingredient in state-ofthe-art software for solving mixed-integer linear programs. In particular, much attention has been paid to the strengthening of these cuts. In this paper, we give an overview of existing approaches for improving the performance of Gomory mixed-integer cuts. More precisely, we consider k-cuts, combined Gomory mixed-integer cuts, reduce-and-split cuts, and lift-and-project cuts. We give a detailed description of the implementation of the separation routines for these cutting planes. Finally, we report on computational results with the different strengthening approaches on a large-scale test set and analyze their performance. We also investigate the characteristics of the generated cutting planes. The results show that, although Gomory mixed-integer cuts are very effective, strengthening these cuts can have a positive impact on the performance of a MIP solver in many cases.