Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25909
Titel: Gomory-Chvátal cutting planes and the elementary closure of Polyhedra
Verfasser: Eisenbrand, Friedrich
Sprache: Englisch
Erscheinungsjahr: 2000
SWD-Schlagwörter: Ganzzahlige Optimierung
Schnittebenenverfahren
Polyeder
Konvexe Hülle
Freie Schlagwörter: Gomory-Chvátal
Schnittebene
elementare Hülle
polyhedrom
cutting planes
rank
elementary closure
DDC-Sachgruppe: 510 Mathematik
Dokumentart : Dissertation
Kurzfassung: 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 zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-13429
hdl:20.500.11880/25965
http://dx.doi.org/10.22028/D291-25909
Erstgutachter: Bockmayr, Alexander
Tag der mündlichen Prüfung: 6-Jul-2000
SciDok-Publikation: 19-Nov-2007
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Dissertation_7143_Eise_Frie_2000.pdf525,11 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.