Polyhedral aspects of cardinality constrained combinatorial optimization problems

Diese Dissertation befasst sich mit polyedrischen Strukturen von kardinalitätsbeschränkten kombinatorischen Optimierungsproblemen. Aus einem kombinatorischen Optimierungsproblem erhält man ein kardinalitätsbeschränktes kombinatorisches Optimierungsproblem, indem man nur solche Lösungen erlaubt, deren Kardinalitäten Elemente einer festgelegten Menge von nichtnegativen ganzen Zahlen sind. Wir beschäftigen uns sowohl mit der polyedrischen Analyse ausgewählter kombinatorischer Optimierungsprobleme als auch mit allgemeinen Methoden, um starke gültige Ungleichungen herzuleiten, die einen Bezug zu Kardinalitätsbeschränkungen haben. Im Mittelpunkt der Arbeit steht die Untersuchung der Facettialstrukturen der kardinalitätsbeschränkten Matroid-, Wege-, und Kreis-Polytope. Wie es exemplarisch für Matroid-, Wege-, und Kreis-Polytope gezeigt wird, ist eine facettendefinierende Ungleichung für ein nicht-kardinalitätsbeschränktes Polytop gewöhnlich auch für die kardinalitätsbeschränkte Version facettendefinierend. Insbesondere interessieren wir uns aber für Ungleichungen, die solche Lösungen abschneiden, die für das Basisproblem zulässig sind, aber nicht für dessen kardinalitätsbeschränkte Version. Die wichtigste Klasse von Ungleichungen sind in diesem Zusammenhang die sogenannten forbidden cardinality inequalities. Das sind Ungleichungen, die für ein mit einem kardinalitätsbeschränkten kombinatorischen Optimierungsproblem assoziiertem Polytop gültig sind, unabhängig von dessen kombinatorischer Struktur. Diese Ungleichungen verwenden wir als Prototyp für Ungleichungen,die kombinatorische Strukturen eines gegebenen Problems einbinden. Auf diese Weise gelingt es uns, für verschiedene kardinalitätsbeschränkte Probleme facettendefinierende Ungleichungen herzuleiten, insbesondere für die oben namentlich genannten Polytope. Außerdem präsentieren wir weitere Klassen facettendefinierender Ungleichungen, die einen Bezug zu Kardinalitätsbeschränkungen haben, für kardinalitätsbeschränkte Wege- und Kreis-Polytope. Insbesondere befassen wir uns auch mit solchen Ungleichungen, die spezifisch für gerade/ungerade Kreise/Wege oder Wege mit höchstens k Kanten sind. Die Arbeit präsentiert und benutzt verschiedene Methoden und Ideen, um starke gültige Ungleichungen, die einen Bezug zu Kardinalitätsbeschränkungen haben, herzuleiten: matroidale Relaxierungen, Lifting, Projektion oder auch algorithmische Aspekte. Es wird beispielsweise gezeigt, dass die dem Moore-Bellman-Ford Algorithmus innewohnende Struktur dazu verwendet werden kann, um facettendefinierende Ungleichungen für das Polytop der gerichteten (s,t)-Wege mit höchstens k Kanten, herzuleiten. Für zwei Relaxierungen dieses Polytops liefert unser Ansatz eine Klassifizierung aller facettendefinierenden Ungleichungen mit Koeffizienten in {0,1} bzw. {-1,0,1}.

Author dc:creator

• Stephan, Rüdiger

Advisor dc:contributor.advisor

• Grötschel, Martin

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en, English

Identifier URI

urn:nbn:de:kobv:83-opus-24018
http://dx.doi.org/10.14279/depositonce-2279

OAI identifier oai:identifier

oai:depositonce.tu-berlin.de:11303/2576