{0,1/2}-Chvátal-Gomory cuts for Integer Linear Programming

Arie Koster (University of Warwick, Centre for Discrete Mathematics and its Applications (DIMAP), Coventry, UK)

Chvátal-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. This talk reports on our study to separate general $\zerohalfset$-cuts effectively, despite its NP-completeness.

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.

Joint work with Manuel Kutschka and Adrian Zymolka.

back to EIDMA Seminar Combinatorial Theory announcements