Untere Schranken für die binäre quadratische Minimierung mithilfe nichtkonvexer separabler Unterschätzer

• Antragsteller: Professor Dr. Christoph Buchheim
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2012 bis 2017
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 231686800

Das Projekt befasst sich mit der Lösung quadratischer Varianten klassischer kombinatorischer Optimierungsprobleme. Diese sind in aller Regel auch dann NP-schwer, wenn die lineare Optimierung über derselben Zulässigkeitsmenge effizient möglich ist. So ist etwa das quadratische Spannbaumproblem nicht nur theoretisch, sondern auch praktisch sehr schwer lösbar, obwohl für die entsprechende lineare Problemvariante bekanntlich sehr effiziente kombinatorische Algorithmen existieren, wie z.B. der Algorithmus von Kruskal.Im Projekt wurde bisher ein neuer Ansatz zur exakten Lösung quadratischer kombinatorischer Optimierungsprobleme entwickelt, der insbesondere für solche Probleme anwendbar ist, bei denen das zugrunde liegende lineare Optimierungsproblem effizient gelöst oder zumindest gut approximiert werden kann. Dabei werden zunächst keine weiteren Annahmen für die quadratische Zielfunktion gemacht, insbesondere muss diese weder konvex noch in irgendeiner Weise dünn besetzt sein.Die Idee des Ansatzes besteht darin, die gegebene quadratische Zielfunktion durch eine separable quadratische Zielfunktion zu unterschätzen (im Falle eines Minimierungs­problems). Aufgrund der Binarität der Variablen ist die separable quadratische Zielfunktion äquivalent zu einer linearen Funktion. Die optimale Lösung des resultierenden linearen Optimierungsproblems liefert also eine untere Schranke für das ursprüngliche quadratische Problem. Durch Einbettung in ein Branch-and-Bound-Verfahren kann somit eine optimale Lösung für das ursprüngliche quadratische Problem berechnet werden. Ein wichtiger Vorteil dieses Ansatz ist es, dass die resultierenden linearen Probleme zur Bestimmung unterer Schranken auf beliebige Weise gelöst werden können, insbesondere können hier auch schnelle kombinatorische Algorithmen verwendet werden. Der Löser der linearen Probleme wird in unserem Ansatz als Black Box betrachtet.Im weiteren Projektverlauf liegt der Schwerpunkt auf der Verbesserung der Methoden und damit verbunden der Beschleunigung der Berechnung. Insbesondere soll für die semidefiniten Programme, die zur Bestimmung optimaler Unterschätzer gelöst werden müssen, ein problemspezifischer Algorithmus entwickelt werden. Desweiteren steht die Frage im Mittelpunkt, wie bei einzelnen kombinatorischen Problemen die Forderung der Separabilität aufgegeben werden kann, um stärkere Schranken zu erhalten. Das Gesamtziel ist ein algorithmischer Ansatz, der einerseits für eine große Klasse von kombinatorischen Optimierungsproblemen direkt einsetzbar ist, indem lediglich die Black Box für das zugrunde liegende lineare Problem eingesetzt werden muss. Andererseits sollen für spezielle Probleme noch deutliche Verbesserungen erreicht werden, insbesondere indem die Problemstruktur für die Berechnung besserer Unterschätzer ausgenutzt wird.

• DFG-Verfahren: Sachbeihilfen