Polyhedral aspects of cardinality constrained combinatorial optimization problems
Stephan, Rüdiger
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}.
This thesis deals with polyhedral structures of cardinality constrained combinatorial optimization problems. Given a combinatorial optimization problem, we obtain a cardinality constrained version of this problem by permitting only those solutions whose cardinalities are elements of a specified set of nonnegative integral numbers. We study both the polyhedral analysis of selected cardinality constrained combinatorial optimization problems and general methods for deriving strong valid inequalities that bear relations to cardinality restrictions. The focus of this thesis is the investigation of the facial structure of the cardinality constrained matroid, path and cycle polytopes. As it might be expected and is exemplarily shown for path, cycle, and matroid polytopes, an inequality that induces a facet of the polytope associated with the ordinary problem usually induces a facet of the polytope associated with the cardinality restricted version. However, we are in particular interested in inequalities that cut off the incidence vectors of solutions that are feasible for the ordinary problem but infeasible for its cardinality restricted version. In this context, the most important class of inequalities for this thesis are the so-called forbidden cardinality inequalities. These inequalities are valid for a polytope associated with a cardinality constrained combinatorial optimization problem independent of its specific combinatorial structure. Using these inequalities as prototype for inequalities incorporating combinatorial structures of a problem, we derive facet defining inequalities for polytopes associated with several cardinality constrained combinatorial optimization problems, in particular, for the above mentioned polytopes. Moreover, for cardinality constrained path and cycle polytopes we derive further classes of facet defining inequalities related to cardinality restrictions, also those inequalities specific to odd/even path/cycles and hop constrained paths. The thesis presents and uses different methods and ideas for deriving strong inequalities related to cardinality restrictions: matroidal relaxations, lifting, projection, and also algorithmic ingredients. For example, it will be shown that the inherent structure of the Moore-Bellman-Ford algorithm can be used to find facet defining inequalities for the hop constrained path polytope, that is, the convex hull of the incidence vectors of paths having at most k arcs. For two relaxations of this polytope, our approach yields a classifications of all facet defining inequalities with coefficients in {0,1} and {-1,0,1}, respectively.
