Geometrie und Algorithmen zur Ausnutzung Polyedrischer Symmetrien

• Antragsteller: Professor Dr. Achill Schürmann
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2015 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 263949937

Viele wichtige Probleme in der Mathematik und ihren Anwendungen werden mit Hilfe lineare Nebenbedingungen modelliert. Die dadurch definierten geometrischen Objekte werden Polyeder genannt. Standardmodellierungen führen häufig zu Polyedern mit vielen Symmetrien, wie zum Beispiel im Falle der sogenannten "Travelling Salesman oder Assignment Polyeder". Trotzdem nutzen Standardalgorithmen wie Branch-and-Bound-Methoden diese Symmetrien nicht aus. Häufig ist es sogar so, dass diese Verfahren besonders schlecht für symmetrischen Probleme funktionieren, obwohl elaborierte mathematische Werkzeuge zur Behandlung von Symmetrien zur Verfügung stehen. In diesem Projekt werden wir neue Techniken zur Symmetrieausnutzung entwickeln, für fundamentale polyhedrische Berechnungen: Für die Darstellungskonvertierung, für die ganzzahlige lineare Programmierung, für das Zählen von Gitterpunkten und die exakte Volumenberechnung. Wir werden dabei erstmals die besonderen geometrischen Eigenschaften nutzen, die duch die affine Symmetriegruppe eines Polyeders impliziert werden. Die neu zu entwickelnden Algorithmen werden dabei auf Ergebnissen aus Disziplinen wie der Geometrie der Zahlen, der Invarianten- oder Gruppentheorie basieren. Die Entwicklung von neuen theoretischen und algorithmischen Hilfsmitteln wird dabei parallel zur Arbeit an herausfordernden mathematischen Problemen verlaufen, die aus unterschiedlichen Bereichen wie der Zahlentheorie, Kombinatorik und Sozialwahltheorie kommen. Auf diese Weise schaffen wir neue, beidseitig fruchtbare Verbindungen zwischen Mathematischer Optimierung und Reiner Mathematik. Unsere Arbeit soll zur Entwicklung öffentlich zugänglicher Software beitragen, und dadurch vielfältige neue Forschungsmöglichkeiten für andere Mathematiker eröffnen. Da die entwickelten geometrischen und algorithmischen Grundlagen helfen werden Symmetrien in vielen zukünftigen Berechnungen auszunutzen, wird dieses Projekt einen nachhaltigen Langzeiteffekt haben, der weit über das Projekt hinausreicht.

• DFG-Verfahren: Sachbeihilfen