Algorithms to Separate {0,1/2}-Chvatal-Gomory Cuts

Please always quote using this URN: urn:nbn:de:0297-zib-9531
  • Chvatal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or $\frac{1}{2}$, such cuts are known as $\{0,\frac{1}{2}\}$-cuts. It has been proven by Caprara and Fischetti (1996) that separation of $\{0,\frac{1}{2}\}$-cuts is NP-hard. In this paper, we study ways to separate $\{0,\frac{1}{2}\}$-cuts effectively in practice. We propose a range of preprocessing rules to reduce the size of the separation problem. The core of the preprocessing builds a Gaussian elimination-like procedure. To separate the most violated $\{0,\frac{1}{2}\}$-cut, we formulate the (reduced) problem as integer linear program. Some simple heuristic separation routines complete the algorithmic framework. Computational experiments on benchmark instances show that the combination of preprocessing with exact and/or heuristic separation is a very vital idea to generate strong generic cutting planes for integer linear programs and to reduce the overall computation times of state-of-the-art ILP-solvers.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Arie M.C.A. Koster, Adrian Zymolka, Manuel Kutschka
Document Type:ZIB-Report
Tag:1/2}-Chvatal-Gomory cuts; integer programming; separation algorithms; {0
MSC-Classification:65-XX NUMERICAL ANALYSIS / 65Kxx Mathematical programming, optimization and variational techniques / 65K05 Mathematical programming methods [See also 90Cxx]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Date of first Publication:2007/05/18
Series (Serial Number):ZIB-Report (07-10)
Published in:An extended abstract appears in: Proc. 15th annual European Symposium on Algorithms, ESA 2007, Eilat, Israel, Lecture Notes in Computer Science 4698, 2007, pp. 693-704