Semidefinite und Polyedrische Relaxierungen für Graphenpartitionsprobleme

• Antragsteller: Professor Dr. Christoph Helmberg
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2003 bis 2006
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5410525

In der Lösung kombinatorischer Optimierungsprobleme haben sich zwei Ansätze in den letzten Jahren besonders bewährt. Zum einen sind dies polyedrische Methoden, in denen neue Erkenntnisse über die zugrundeliegenden Polyeder in LP-basierten Branch-and Bound Verfahren in Form zusätzlicher Schnittebenen einfließen. Die zweite sehr erfolgreiche Methode verwendet Konzepte der Semidefiniten Optimierung, indem die lineare Anfangsrelaxierung des ersten Ansatzes durch eine schärfere semidefinite ersetzt wird. Mit diesen semidefiniten Relaxierungen konnten beeindruckende Ergebnisse bei der Entwicklung von Approximationsalgorithmen erzielt werden. Bei der Lösung praxisrelevanter Probleme dominieren jedoch deutlich lineare Methoden. Bislang gibt es nur vereinzelt Versuche, die positiven Aspekte beider Methoden zu vereinen. Das Ziel des beantragten Projektes ist es, am Beipiel von Graphenpartitionsproblemen - ein kombinatorisches Optimierungsproblem von hoher praktischer Bedeutung - beide Ansätze zusammenzuführen und zu untersuchen, ob semidefinite Methoden mit rein polyedrischen Ansätzen auch für große Probleminstanzen konkurrenzfähig sind, inwieweit sich beide befruchtend kombinieren lasen, und von welcher Qualität die dabei erzielten Lösungen und Ergebnisse sind.

• DFG-Verfahren: Sachbeihilfen