Please use this identifier to cite or link to this item: doi:10.22028/D291-25909
Title: Gomory-Chvátal cutting planes and the elementary closure of Polyhedra
Author(s): Eisenbrand, Friedrich
Language: English
Year of Publication: 2000
SWD key words: Ganzzahlige Optimierung
Schnittebenenverfahren
Polyeder
Konvexe Hülle
Free key words: Gomory-Chvátal
Schnittebene
elementare Hülle
polyhedrom
cutting planes
rank
elementary closure
DDC notations: 510 Mathematics
Publikation type: Doctoral Thesis
Abstract: The elementary closure P'; of a polyhedrom P is the intersection of P with all its Gomory-Chvátal cutting planes. P'; is a rational polyhedron provided that P is rational. The Chvátal-Gomory procedure is the iterative application of the elementary closure operation to P. The Chvátal rank is the minimal number of iterations needed to obtain P_I. It is always finite, but already in |R² one can construct polytopes of arbitrary large Chvátal rank. We show that the Chvátal rank of polytopes contained in the n-dimensional 0/1 cube is O(n² log n) and prove the lower bound (1+E) n, for some E> 0. We show that the separation problem for the elementary closure of a rational polyhedron is NP-hard. This solves a problem posed by Schrijver. Last we consider the elementary closure in fixed dimension. the known bounds for the number of inequalities defining P'; are exponential, even fixed dimension. We show that the number of inequalities needed to describe the elementary closure of a rational polyhedron is polynomially bounded in fixed dimension. Finally, we present a polynomial algorithm in varying dimension, which computes cutting planes for a simplicial cone from this polynomial description in fixed dimension with a maximal degree of violation in a natural sense.
Die elemtare Hülle P'; eines Polyeders P ist der Durchschnitt von P mit all seinen Gomory-Chvátal Schnittebenen. P'; ist ein rationales Polyeder, falls P rational ist. Die Chvátal-Gomory Prozedur ist das wiederholte Bilden der elementaren Hülle, beginnend mit P. Die minimale Anzahl der Iterationen, die bis zum Erhalt der ganzzahligen Hülle P1 von P nötig sind, heißt Chvátal-Rang von P. Der Chvátal-Rang eines rationalen Polyeders ist endlich. Jedoch lassen sich bereits im |R² Beispiele mit beliebig hohem Chvátal-Rang konstruieren. Wir zeigen, dass der Chvátal-Rang eines Polytops im n-dimensionalen 0/1 Würfel durch O(n² log n) beschränkt ist, und beweisen die untere Schranke (1 + epsilon) * n, für ein epsilon > 0. Wir zeigen, dass das Separationsproblem für die elementare Hülle eines rationalen Polyeders NP-hart ist. Dies löst ein von Schrijver formuliertes Problem. Schließlich wenden wir uns der elementaren Hülle rationaler Polyeder in fester Dimension zu. Die bislang bekannten Schranken für die Anzahl der Ungleichungen, die zur Darstellung von P'; benötigt werden, sind exponentiell, selbst in fester Dimension. Wir zeigen, dass in fester Dimension P'; durch polynomiell viele Ungleichungen beschrieben werden kann. Wir entwerfen außerdem einen, in beliebiger Dimension polynomiellen, Algorithmus, der zu einem spitzen Kegel P eine Schnittebene aus der polynomiellen Darstellung von P'; berechnet, die zudem einen maximalen Grad der Verletzung in einem natürlichen Sinne aufweist.
Link to this record: urn:nbn:de:bsz:291-scidok-13429
hdl:20.500.11880/25965
http://dx.doi.org/10.22028/D291-25909
Advisor: Bockmayr, Alexander
Date of oral examination: 6-Jul-2000
Date of registration: 19-Nov-2007
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
Dissertation_7143_Eise_Frie_2000.pdf525,11 kBAdobe PDFView/Open


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.