Semidefinite and polyhedral relaxations for graph partitioning problems

• Applicant: Professor Dr. Christoph Helmberg
• Subject Area: Mathematics
• Term: from 2003 to 2006
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants