Embedding {0, ½}-Cuts in a Branch-and-Cut Framework: A Computational Study

Embedding {0, ½}-Cuts in a Branch-and-Cut Framework: A Computational Study

0.00 Avg rating0 Votes
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: , ,
Abstract:

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.

Reviews

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