Grundlegende Untersuchungen zur Reduktion von Symmetrie in ganzzahligen linearen Optimierungsmodellen mit Hilfe linearer Ungleichungen

• Applicant: Professor Dr. Volker Kaibel
• Subject Area: Mathematics
• Term: from 2009 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 81958761

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 dieses 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 Fällen 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 ist die systematische Untersuchung der grundsätzlichen Möglichkeiten, auf diese Weise Symmetriereduktion in ganzzahligen linearen Optimierungsmodellen vorzunehmen. Zu diesem Zweck werden von uns eingeführte Symmetriebrechungs-Polytope (Orbitope) umfassend untersucht. Erste Experimente haben bereits gezeigt, dass vertieftes Wissen über diese Orbitope bei einigen zuvor praktisch unlösbaren Optimierungsmodellen die Lösung ermöglicht.

• DFG Programme: Research Grants