Synergien zur exakten Lösung des Maximum Schnitt Problems

Eine Vielzahl von Anwendungen in Bereichen wie Physik, Data Science, Logistik, Telekommunikation und Finanzen kann als binäre quadratische Optimierungsprobleme oder äquivalente Max-Cut-Probleme modelliert werden. Der Begriff "binär" bezieht sich auf Variablen, die auf die Werte null oder eins beschränkt sind und die Grundlage dieser mathematischen Modelle bilden. Obwohl diese Probleme hochrelevant sind, liegen Instanzen mit einer großen Zahl an Variablen außerhalb der Möglichkeiten bestehender Standardtools, was eine starke Nachfrage nach fortschrittlichen Lösungsansätzen erzeugt. Algorithmen zur Bewältigung dieser Probleme basieren entweder auf Linear Programming (LP) oder Semidefinite Programming (SDP). Dieses Projekt schlägt einen synergetischen Ansatz vor, der diese bislang unabhängig entwickelten Methoden integriert und verbessert, um so eine neuartige Lösung zur exakten Lösung komplexer binärer quadratischer Probleme zu bieten. Ziel des Projektes ist die Entwicklung eines exakten Solvers, der, wo immer möglich, freie und akademische Softwarebibliotheken verwendet und mit fortschrittlichen algorithmischen Ansätzen bestehende Methoden kombiniert. Dieser Solver wird einerseits allgemeine Problemstellungen adressieren und andererseits auch spezielle Anpassungen für domänenspezifische Herausforderungen beinhalten, wie beispielsweise für Spin-Glas-Instanzen aus der Physik. Darüber hinaus wird das Projekt die Solver mit gemeinsamen Analyse-, Vorverarbeitungs- und Zerlegungsmodulen in einem einheitlichen Framework kombinieren, das der Scientific Community als webbasierter Dienst angeboten wird. Zum ersten Mal werden LP- und SDP- basierte Lösungsansätze integriert, wodurch neue Synergien und gegenseitige Verbesserungen ermöglicht werden. Außerdem wird eine Instanzbibliothek erstellt, die numerische Experimente unterstützt und einen soliden Benchmark-Satz bereitstellt. Die Zusammenarbeit in diesem Projekt vereint Expert:innen aus komplementären Bereichen. Forscher:innen der Universität Bonn bringen Fachwissen zu linearen Programmieransätzen für komplexe Optimierungsprobleme ein, während Expert:innen der Alpen-Adria-Universität Klagenfurt für ihre umfangreiche Arbeit bei SDP-Algorithmen und akademischer Software anerkannt sind. Gemeinsam zielen sie darauf ab, transformative Werkzeuge zur Lösung großskaliger Optimierungsprobleme zu entwickeln und dadurch sowohl die Forschung als auch praktische Anwendungen voranzubringen.