zbMATH — the first resource for mathematics

Embedding \(\{0, \frac{1}{2}\}\)-cuts in a branch-and-cut framework: a computational study. (English) Zbl 1241.90181
Summary: 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, \frac{1}{2}\}\) 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.

90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C10 Integer programming
Full Text: DOI