Synergien zur exakten Lösung des Maximum Schnitt Problems

• Antragsteller: Dr. Sven Mallach
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 537033028

Wir stellen einen synergetischen Ansatz zur exakten Lösung des Maximum Schnitt Problems und des unrestringierten Binär-Quadratischen Optimierungsproblems vor, der bisher getrennt entwickelte State-of-the-Art Techniken basierend auf Ganzzahliger Linearer Optimierung (ILP) sowie auf Semidefiniter Optimierung (SDP) auf neue Weise integriert und gemeinsam weiterentwickelt. Das synergetische Zusammenspiel beider Methoden geschieht dabei auf (mindestens) zwei Ebenen. Einerseits kombinieren wir ILP- und SDP-basierte Algorithmen erstmals in einem gemeinsamen Divide-and-Conquer Ansatz, der es ermöglicht, Probleminstanzen zu lösen, die außerhalb der Möglichkeiten der einzelnen heutigen State-of-the-Art Lösern liegen. Darüber hinaus werden wir die beiden Techniken auch im Sinne eines Preprocessings für die jeweils andere Methode sinnvoll miteinander verbinden, um sie hinsichtlich der Lösung schwieriger Probleminstanzen zu verbessern. Andererseits werden wir unsere ILP- und SDP-Ansätze gemeinsam methodisch verbessern. Ein kurzer Überblick über unsere diesbezüglich geplanten Entwicklungen umfasst algorithmische Innovationen für hochentwickelte Löserkomponenten wie Separationsalgorithmen und Problemzerlegungsstrategien, eine gründliche Analyse und Erweiterung von Preprocessing-Techniken, sowie algorithmische Weiterentwicklungen mittels einer strukturellen Untersuchung von Probleminstanzen und der Performanz der verschiedenen Algorithmen, die in einen Algorithm Engineering Zyklus eingebettet ist. Während die Fortentwicklung aktueller State-of-the-Art Algorithmen im Zentrum unseres Vorhabens steht, werden wir darüber hinaus auch einen exakten Löser beitragen, der ausschließlich Unterroutinen freier und akademischer anstatt kommerzieller Softwarebibliotheken verwendet, insbesondere um weitere Forschungsentwicklungen zu begünstigen. Zudem werden wir auch die aktuellen State-of-the-Art Dienste zur Lösung von Spin Glass Instanzen durch spezialisierte Varianten unserer neuen Methoden verbessern. Sowohl zur Unterstützung der wissenschaftlichen Community als auch unserer Vorhaben werden wir zudem eine große und diversifizierte Probleminstanzbibliothek aufbauen, die auch nützliche Metadaten und verschiedene Dateiformate bereitstellt. Schließlich werden wir mit unserem Vorhaben zum ersten Mal eine (ultimativ faire) Grundlage für einen experimentellen Vergleich von ILP- und SDP-Ansätzen basierend auf demselben Preprocessing-Workflow schaffen.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Österreich
• Partnerorganisation: Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
• Kooperationspartnerin: Professorin Dr. Angelika Wiegele