The maximum feasible subsystem problem and vertex-facet incidences of polyhedra (2003)

Hauptmotivation dieser Arbeit ist die Untersuchung des so genannten Maximum Feasible Subsystem problems (MaxFS) aus der kombinatorischen Optimierung, das folgendermaßen formuliert werden kann: Gegeben ist ein unzulässiges lineares Ungleichungssystem und gesucht ist ein möglichst großes zulässiges Teilsystem. Für dieses NP-schwere Problem gibt es eine Vielzahl interessanter praktischer Anwendungen. Das erste Kapitel beschäftigt sich mit grundlegenden Eigenschaften des MaxFS-Problems. Zunächst wird eine neue geometrische Charakterisierung von minimalen unzulässigen Teilsystemen vorgestellt und dann gezeigt, dass das Problem, ein solches Teilsystem möglichst kleiner Kardinalität zu finden, NP-schwer ist. Danach wird das zu MaxFS assoziierte Polytop P_FS untersucht, welches die konvexe Hülle aller Inzidenzvektoren von zulässigen Teilsystemen des gegebenen Ungleichungssystems ist; dieses bietet die Grundlage für eine polyedrische Behandlung von MaxFS durch Branch-and-Cut-Algorithmen, z.B. im fünften Kapitel. Es wird zunächst (erneut) bewiesen, dass Ungleichungen, die zu minimalen unzulässigen Teilsystemen gehören, Facetten von P_FS definieren. Dann wird charakterisiert, unter welchen Bedingungen die von so genannten verallgemeinerten Antiwebs stammenden Ungleichungen Facetten definieren. Hierfür werden Resultate aus dem dritten Kapitel verwendet. Im zweiten Kapitel werden so genannte IIS-Hypergraphen untersucht; dabei entspricht jeder Knoten des Hypergraphen einer Ungleichung eines unzulässigen Systems Sigma: {A x <= b} und jede Kante einem minimal unzulässigen Teilsystem (IIS) von Sigma. Es wird bewiesen, dass das zugehörige Erkennungsproblem NP-schwer ist, wobei folgender, für diese Arbeit fundamentaler Zusammenhang benutzt wird: Ein IIS entspricht genau dem Träger einer Ecke des zu Sigma gehörigen Alternativpolyeders. Danach wird bewiesen, dass es auch keine Charakterisierung von IIS-Hypergraphen durch eine endliche Menge ausgeschlossener Minoren geben kann. Im dritten Kapitel werden Ecken-Facetten Inzidenzen von (unbeschränkten) Polyedern untersucht. Es stellt sich heraus, dass im Allgemeinen der Seitenflächenverband eines unbeschränkten Polyeders nicht aus seinen Inzidenzen rekonstruiert werden kann. Es ist jedoch möglich, an den Inzidenzen eines Polyeders festzustellen, ob es unbeschränkt oder beschränkt ist. Weiterhin wird bewiesen, dass es keine unbeschränkten d-Polyeder mit folgenden Eigenschaften gibt: d ist mindestens 2, in jeder Facette liegen d Ecken (simplizial) und jede Ecke ist in d Facetten enthalten (einfach). Die Resultate dieses Kapitels werden maßgeblich im ersten und zweiten Kapitel verwendet. Ein Algorithmus zum effizienten Berechnen des (Hasse-Diagramms des) Seitenflächenverbandes eines Polytopes aus seinen Ecken-Facetten-Inzidenzen wird im vierten Kapitel vorgestellt. Einige interessante Spezialfälle werden diskutiert, wovon einer auch im dritten Kapitel Anwendung findet. Im fünften Kapitel wird eine Implementierung eines Branch-and-Cut-Algorithmus zur Läsung des MaxFS-Problems vorgestellt. Diese Implementierung wird auf verschiedenen Testinstanzen evaluiert.