Optimization Online


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

Arie M.C.A. Koster (Arie.Koster***at***wbs.ac.uk)
Adrian Zymolka (zymolka***at***atesio.de)
Manuel Kutschka (kutschka***at***zib.de)

Abstract: 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.

Keywords: {0,1/2}-Chvatal-Gomory cuts, separation algorithms, integer programming

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )

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.

Download: [PDF]

Entry Submitted: 07/31/2007
Entry Accepted: 08/01/2007
Entry Last Modified: 08/02/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society