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

• Final Report Year: 2007

Final Report Abstract

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.

Publications

• (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.