Article ID: | iaor200916826 |
Country: | United States |
Volume: | 19 |
Issue: | 2 |
Start Page Number: | 229 |
End Page Number: | 238 |
Publication Date: | Apr 2007 |
Journal: | INFORMS Journal On Computing |
Authors: | Fischetti Matteo, Caprara Alberto, Andreello Giuseppe |
Embedding cuts into a branch–and–cut framework is a delicate task, especially when a large set of cuts is available. In this paper we describe a separation heuristic for {0, ½} cuts, a special case of Chvátal–Gomory cuts, that tends to produce many violated inequalities within relatively short time. We report computational results on a large testbed of integer linear programming (ILP) instances of combinatorial problems including satisfiability, max–satisfiability, and linear ordering problems, showing that a careful cut–selection strategy produces a considerable speedup with respect to the cases in which either the separation heuristic is not used at all, or all of the cuts it produces are added to the LP relaxation.