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 1/2, such cuts are known as {0, 1/2}-cuts. It has been proven by Caprara and Fischetti (1996) that separation of {0, 1/2}-cuts is NP-hard. In this paper, we study ways to separate {0, 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, 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.
Citation
ZIB-Report 07-10, http://www.zib.de/Publications/abstracts/ZR-07-10 An extended abstract appears in Proceedings of the 15th European Symposium on Algorithms, ESA 2007.