Reduction of the complexity of linear models for combinatorial optimization problems via formulations in space of higher dimensions
Final Report Abstract
In der Kombinatorischen Optimierung hat sich in den vergangenen Jahrzehnten der Ansatz, Techniken der Linearen Optimierung auf die konvexe Hülle einer die zulässigen Lösungen des Problems geeignet kodierenden Punktmenge anzuwenden, als sehr erfolgreich heraus gestellt. Für viele Probleme wurden die zugehörigen Polytope (also jene konvexen Hüllen) sehr intensiv studiert. In den meisten interessanten Fällen haben diese Polytope allerdings exponentiell in der Größe der Probleminstanz viele Facetten, so dass für den linearen Optimierungsansatz exponentiell viele Nebenbedingungen beachtet werden müssen. Obwohl diese riesigen Systeme oft effizient implizit behandelt werden können, ist es sehr wünschenswert, deutlich kleinere Systeme zu identifizieren, die explizit benutzt werden können, z.B. um Standard-Software einzusetzen. Das Konzept der erweiterten Formulierungen dient diesem Ziel, indem Polytope als affine Projektionen höher-dimensionaler, aber wesentlich einfacher zu beschreibender Polyeder dargestellt werden. Für eine Reihe von Problemen ist dies in der Tat in der Vergangenheit bereits gelungen. Das Ziel dieses Projekts war, das grundlegende Verständnis des Konzepts der erweiterten Formulierungen zu verbessern und neue Methoden sowohl für die Konstruktion als auch für die Bestimmung unterer Schranken an die kleinste mögliche Größe solcher Formulierungen zu entwickeln. Die wichtigsten Ergebnisse des Projekts sind auf der konstruktiven Seite die Entwicklung kleiner erweiterter Formulierungen für mit nicht-linearen Spannbaumproblemen assoziierte Polytope, für Unabhängigkeitspolytope von Count-Matroiden und für Subgraph-Polytope. Im Hinblick auf untere Schranken an die Größe von erweiterten Formulierungen etablierten wir die bisher beste Schranke für das Correlation-Polytop sowie eine allgemeine Methode zum Nachweis, dass in einer Klasse von Polytopen solche enthalten sind, die keine kleinen erweiterten Formulierungen erlauben. Zudem konnten wir nachweisen, dass es beispielsweise für Spannbaumpolytope keine kleinen nicht-degenerierten erweiterten Formulierungen gibt. Ein zur strukturellen Einordnung wichtiges Resultat ist eine Charakterisierung der Schlupfmatrizen von Polytopen, die in der Theorie der erweiterten Formulierungen eine zentrale Rolle spielen.
Publications
- A short proof that the extension complexity of the correlation polytope grows exponentially, Discrete & Computational Geometry 53 (2015), no. 2, 396–401
Volker Kaibel and Stefan Weltge
(See online at https://doi.org/10.1007/s00454-014-9655-9) - Simple extensions of polytopes, Math. Program. Ser. B 154 (2015), no. 1-2, 381–406
Volker Kaibel and Matthias Walter
(See online at https://doi.org/10.1007/s10107-015-0885-2) - Sizes of linear descriptions in combinatorial optimization, Ph.D. thesis, Otto-von-Guericke Universität Magdeburg, 2015
Stefan Weltge
(See online at https://doi.org/10.25673/4350) - Subgraph polytopes and independence polytopes of count matroids, Operations Research Letters 43 (2015), no. 5, 457 – 460
Michele Conforti, Volker Kaibel, Matthias Walter, and Stefan Weltge
(See online at https://doi.org/10.1016/j.orl.2015.06.011) - Maximum semidefinite and linear extension complexity of families of polytopes, Math. Program. 167 (2018), no. 2, 381 – 394
Gennadiy Averkov, Volker Kaibel, and Stefan Weltge
(See online at https://doi.org/10.1007/s10107-017-1134-7) - Extended formulations for higher order polytopes in combinatorial optimization, Ph.D. thesis, Otto-von-Guericke Universität Magdeburg, 2019
Mirjam Friesen
(See online at https://doi.org/10.25673/25397)
