Eingang zum Volltext

Urheberrechtshinweis / Copyright notice

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://opus.kobv.de/zib/volltexte/2007/953/

Koster, Arie M.C.A. ; Zymolka, Adrian ; Kutschka, Manuel

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

pdf-Format:
Dokument 1.pdf (333 KB)
ps-Format:
Dokument 1.ps (6.407 KB)

Kurzfassung in Englisch

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.

Freie Schlagwörter (englisch): {0 , 1/2}-Chvatal-Gomory cuts , separation algorithms , integer programming
MSC - Klassifikation 90C10
MSC - Klassifikation 90C57
MSC - Klassifikation 65K05
Abteilung: ZIB Allgemein
DDC-Sachgruppe: Allgemeines, Wissenschaft
Dokumentart: ZIB-Report
Schriftenreihe: ZIB-Report
Band Nummer: 07-10
Quelle: 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
Sprache: Englisch
Erstellungsjahr: 2007
Publikationsdatum: 18.05.2007
Bemerkung: printed version not available / keine gedruckte Version verfügbar

Metadatensuche | Volltextsuche | Browsen | Die neuesten Publikationen | Veröffentlichen
Fragen und Anregungen an bibliothek@zib.de
Letzte Änderung: