Grundlegende Untersuchungen zur Reduktion von Symmetrie in ganzzahligen linearen Optimierungsmodellen mit Hilfe linearer Ungleichungen
Final Report Abstract
Ganzzahlige lineare Optimierungsprobleme spielen eine herausragende Rolle in der modernen Mathematischen Optimierung, z.B. auf Anwendungsfeldern wie der Planung von Telekommunikations- oder Verkehrsnetzen. In den vergangenen Jahrzehnten sind sehr leistungsfähige Algorithmen und Softwarepakete für diese Problem entwickelt worden, die jedoch bei bestimmten Typen von Probleminstanzen versagen. Ein häufiger Grund dafür sind symmetrische Strukturen wie sie zum Beispiel auftreten, wenn man durch Umnummerierungen aus einer Lösung eine große Zahl völlig gleichwertiger Lösungen produzieren kann. Das führt auch bei hoch entwickelter Standard-Software dazu, dass die gleiche Arbeit immer wieder verrichtet werden muss, ohne dass der Algorithmus dies merkt und verhindert. Hochgradig symmetrische Probleme werden daher nur durch konsequente Ausnutzung der Symmetrie lösbar. Eine in diesen Fallen oft angewendete Strategie besteht darin, durch Hinzufügen von (linearen) Restriktionen die Lösungsmenge so zu verkleinern, dass aus den Klassen gleichwertiger Lösungen jeweils nur eine Lösung übrig bleibt. Hauptziel dieses Projekts war die systematische Untersuchung der grundsätzlichen Möglichkeiten, auf diese Weise Symmetriereduktion in ganzzahligen linearen Optimierungsmodellen vorzunehmen. Zu diesem Zweck wurden von uns eingeführte Symmetriebrechungs-Polytope (Orbitope) umfassend untersucht. Diese Klasse von Polytopen enthält nicht nur für die Praxis des Lösens symmetrischer ganzzahliger linearer Optimierungsmodelle sehr wertvolle Objekte, sondern sie bot auch zahlreiche Anknüpfungspunkte für die Weiterentwicklung mathematischer Methodik, die sich als fruchtbar für nicht unmittelbar mit der Symmetriereduktion zusammenhängende Probleme der polyedrischen Kombinatorik erwiesen. So ist das Ergebnis dieses Projekts nicht nur ein vertieftes Verständnis der Möglichkeiten, mittels linearer Einschränkungen Symmetrieausnutzung in der ganzzahligen linearen Optimierung zu betreiben, sondern die Arbeiten haben beispielsweise auch zu neuen Konstruktionsmechanismen für erweiterte Formulierungen geführt.
Publications
- Extended Formulations for Packing and Partitioning Orbitopes. Math. Oper. Res., 2009, 34 (3), 686–697
Yuri Faenza, Volker Kaibel
- Branched Polyhedral Systems. In: Integer Programming and Combinatorial Optimization. Proceedings of IPCO XIV, Ithaca, NY, Friedrich Eisenbrand, Bruce F. Shepherd (Hrsg.), Lecture Notes in Computer Science 6080, Springer, 2010, 177–190
Volker Kaibel, Andreas Loos
- Describing Orbitopes by Linear Inequalities and Projection Based Tools. Dissertation, Fakultät für Mathematik, Otto-von-Guericke Universität Magdeburg, 2011
Andreas Loos
- Finding Descriptions of Polytopes via Extended Formulations and Liftings. In: “Progress in Combinatorial Optimization” (A. R. Mahjoub, Hrsg.), Wiley, 2011, 151-169
Volker Kaibel, Andreas Loos
- Orbitopal fixing. Discr. Optimization, 2011, 8 (4), 595–610
Volker Kaibel, Matthias Peinhardt, Marc E. Pfetsch
