NWO-DFG Ausnutzung von Symmetrien für schnelle Bilevel-Optimierungs-Algorithmen

• Antragsteller: Professor Dr. Martin Schmidt
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung seit 2026
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 567152707

Die Bilevel-Optimierung (BO) ist ein weit verbreitetes mathematisches Werkzeug zur Modellierung hierarchischer Entscheidungsprozesse, bei denen zwei Akteure beteiligt sind: ein sogenannter Leader und ein sogenannter Follower. In Anwendungen der Terrorismusbekämpfung sichert der Leader beispielsweise eine Infrastruktur, um die Auswirkungen der Angriffe des Followers zu minimieren. Weitere Anwendungen finden sich beispielsweise im Bereich der Energienetzwerkplanung (ENP). Um optimale Lösungen für solche BO-Probleme zu finden, wurden viele Techniken aus dem verwandten Bereich der gemischt-ganzzahligen Programmierung (MIP) auf BO übertragen. Die heutige BO-Technologie kann jedoch nur Probleme relativ kleiner Größe lösen, da diese MIP-Techniken unabhängig voneinander betrachtet werden. Durch die Kombination verschiedener Techniken können Synergien geschaffen werden, die dringend erforderlich sind, um reale Probleme, beispielsweise in der heutigen ENP, zu lösen. Dies erfordert jedoch Fachwissen über die jeweiligen Techniken, was für einen einzelnen Forscher und einen monodisziplinären Ansatz eine große Herausforderung darstellt. Das ehrgeizige Ziel dieses kollaborativen Projekts ist es, erstmals Symmetrien und BO-Schnittebenen zu kombinieren. Die leitenden PIs sind führende Experten in ihren jeweiligen Bereichen und bringen eine einzigartige Expertise mit, die für die Umsetzung dieser Forschung erforderlich ist. Bei Erfolg des Projekts werden enorme Leistungssteigerungen erzielt, die es ermöglichen, realistischere BO-Probleme zu lösen – beispielsweise Energienetzwerke mit Hunderten von Knoten anstelle von Dutzenden. Daher entwickeln wir erstmals eine neuartige mathematische Theorie der Bilevel-Symmetrien sowie effektive Algorithmen zur Handhabung dieser Symmetrien. Die MIP-Literatur hat Symmetrien hauptsächlich dazu genutzt, Algorithmen zu beschleunigen, indem symmetrische Bereiche des Lösungsraums eines Problems ausgeschlossen wurden. Neben der klassischen Behandlung von Symmetrien besteht unsere bahnbrechende Idee darin, die bestehende BO-Technologie durch die Berücksichtigung von Symmetrien zu stärken. Dies führt zu einer wesentlich stärkeren Kopplung zwischen den Aktionen des Leaders und des Followers, was letztlich zu effektiveren Algorithmen zur Lösung von BO-Problemen führen wird. In diesem Projekt setzt unser internationales Team (Eindhoven, Trier) diese innovativen Ideen um, indem es eine neue Theorie der Bilevel-Symmetrien entwickelt, Algorithmen zur Behandlung von Symmetrien im MIP-Bereich auf die BO überträgt und neuartige, speziell für BO zugeschnittene Symmetriebehandlungsalgorithmen entwirft. Alle unsere theoretisch entwickelten Techniken werden zudem in modernster Open-Source-BO-Software implementiert, sodass sowohl Forschende als auch PraktikerInnen aus verschiedenen Bereichen, z. B. der Wirtschaft und dem Ingenieurwesen, unmittelbar davon profitieren können, indem sie ihre Probleme schneller mit unserer Software lösen.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Niederlande
• Kooperationspartner: Professor Dr. Christopher Hojny