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

• Erstellungsjahr: 2007

Zusammenfassung der Projektergebnisse

Im Projekt wurde ein SDP-basierter Branch-and-Cut-Zugang für das Minimum Bisection Problem auf großen, dünnbesetzten Graphen betrachtet. Neben neuen polyedrischen Resultaten konnten wir zeigen, dass unser SDP-basierter Zugang sowohl zu neuesten LP-basierten Verfahren wie auch zu bekannten SDP-basierten Verfahren konkurrenzfähig ist und diese in vielen Fällen überflügelt. Mehrere aus der Literatur bekannte Probleminstanzen konnten zum ersten Mal exakt gelöst werden. Für viele andere wurde die Lücke zwischen primaler und dualer Schranke signifikant verkleinert. Somit konnten wir zeigen, dass – im Gegensatz zur bisher herrschenden Meinung – semidefinite Optimierung in Verbindung mit Branch-and-Cut zur exakten Lösung von dünnbesetzten, großen Graphenpartitionierungsproblemen erfolgreich eingesetzt werden kann.

Projektbezogene Publikationen (Auswahl)

• (2006): Hybrid Genetic Algorithm Within Branch-and-Cut for the Minimum Graph Bisection Problem. Gottlieb, J., Raindl, G.R. (Eds.): EvoCOP 2006, LNCS 3906, pp. 1-12
  Armbruster, M., Fügenschuh, M., Helmberg, C., Jetchev, N., Martin, A.
  
• (2006): LP-Based Genetic Algorithm for the Minimum Graph Bisection Problem. Operations Research Proceedings, Volume 2005, pp. 315-320
  Armbruster, M., Fügenschuh, M., Helmberg, C., Jetchev, N., Martin, A.
  
• (2007): Branch-and-Cut for a Semidefinite Relaxation of the a Minimum Bisection Problem. Dissertation, Technische Universität Chemnitz, Deutschland
  Armbruster, M.
  
• (2007): Relaxations and Solutions for the Minimum Graph Bisection Problem. Dissertation, Fachbereich Mathematik der Technischen Universität Darmstadt, Deutschland
  Fügenschuh, M.