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

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.