Reduction of the complexity of linear models for combinatorial optimization problems via formulations in space of higher dimensions

• Antragsteller: Professor Dr. Volker Kaibel
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2012 bis 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 214884184

• Erstellungsjahr: 2019

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

• 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
  
• Simple extensions of polytopes, Math. Program. Ser. B 154 (2015), no. 1-2, 381–406
  Volker Kaibel and Matthias Walter
  
• Sizes of linear descriptions in combinatorial optimization, Ph.D. thesis, Otto-von-Guericke Universität Magdeburg, 2015
  Stefan Weltge
  
• 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
  
• 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
  
• Extended formulations for higher order polytopes in combinatorial optimization, Ph.D. thesis, Otto-von-Guericke Universität Magdeburg, 2019
  Mirjam Friesen