Zugl.: Darmstadt, Techn. University, Diss., 2007.

Universiẗat, Diss., 2001--Bonn.

Bei der Partitionierung von Graphen versucht man, Strukturen in Graphen zu finden (etwa 3-Färbungen oder kleine Bisektionen). Mithilfe von Eigenwerten und Eigenvektoren können solche Probleme oftmals effizient gelöst werden. Wir stellen einen Algorithmus vor, der auf einem sehr allgemeinen Modell für zufällige Graphen bewiesenermaßen sehr gute Dienste leistet. Weiterhin untersuchen wir zufällige 3Sat-Formeln. Hier wollen wir mit Eigenwerten obere Schranken an die Anzahl der erfüllbaren Klauseln finden. Die gefundenen Schranken sind (in den meisten Fällen) nahezu optimal.

This thesis deals with the exact solution of large-scale minimum bisection problems via a semidefinite relaxation in a branch-and-cut framework. After reviewing known results on the underlying bisection cut polytope a study of new facet-defining inequalities is presented. They are derived from the known knapsack tree inequalities. We investigate strengthenings based on the new cluster weight polytope and present polynomial separation algorithms for special cases. The dual of the semidefinite relaxation of the minimum bisection problem is tackled in its equivalent form as an eigenvalue optimisation problem with the spectral bundle method. Implementational details regarding primal heuristics, branching rules, so-called support extensions for cutting planes and warm start are presented. We conclude with a computational study in which we show that our approach is competetive to state-of-the-art implementations using linear programming or semidefinite programming relaxations. / Diese Dissertation befasst sich mit der exakten Lösung großer Minimum Bisection Probleme über eine semidefinite Relaxierung in einem Branch-and-Cut Zugang. Nachdem bekannte Resultate zum zugrundeliegenden Bisection Cut Polytop dargestellt wurden, wird eine Studie neuer facettendefinierender Ungleichungen präsentiert. Diese werden von den bekannten Knapsack Tree Ungleichungen abgeleitet. Wir untersuchen Verstärkungen basierend auf dem neuen Cluster Weight Polytop und zeigen polynomiale Separierungsalgorithmen für Spezialfälle. Die Duale der semidefiniten Relaxierung des Minumum Bisection Problems wird in ihrer äquivalenten Form als Eigenwertoptimierungsproblem mit dem Spektralen Bündelverfahren bearbeitet. Details der Implementierung bezüglich primaler Heuristiken, Branchingregeln, sogenannter Supporterweiterungen für die Schnittebenen und Warmstart werden präsentiert. Wir beenden die Arbeit mit einer numerischen Studie, in der wir zeigen, dass unser Zugang konkurrenzfähig zu aktuellen Implementationen basierend auf linearen und semidefiniten Relaxierungen ist.

Bei der Partitionierung von Graphen versucht man, Strukturen in Graphen zu finden (etwa 3-Färbungen oder kleine Bisektionen). Mithilfe von Eigenwerten und Eigenvektoren können solche Probleme oftmals effizient gelöst werden. Wir stellen einen Algorithmus vor, der auf einem sehr allgemeinen Modell für zufällige Graphen bewiesenermaßen sehr gute Dienste leistet. Weiterhin untersuchen wir zufällige 3Sat-Formeln. Hier wollen wir mit Eigenwerten obere Schranken an die Anzahl der erfüllbaren Klauseln finden. Die gefundenen Schranken sind (in den meisten Fällen) nahezu optimal.

This thesis deals with the exact solution of large-scale minimum bisection problems via a semidefinite relaxation in a branch-and-cut framework. After reviewing known results on the underlying bisection cut polytope a study of new facet-defining inequalities is presented. They are derived from the known knapsack tree inequalities. We investigate strengthenings based on the new cluster weight polytope and present polynomial separation algorithms for special cases. The dual of the semidefinite relaxation of the minimum bisection problem is tackled in its equivalent form as an eigenvalue optimisation problem with the spectral bundle method. Implementational details regarding primal heuristics, branching rules, so-called support extensions for cutting planes and warm start are presented. We conclude with a computational study in which we show that our approach is competetive to state-of-the-art implementations using linear programming or semidefinite programming relaxations. / Diese Dissertation befasst sich mit der exakten Lösung großer Minimum Bisection Probleme über eine semidefinite Relaxierung in einem Branch-and-Cut Zugang. Nachdem bekannte Resultate zum zugrundeliegenden Bisection Cut Polytop dargestellt wurden, wird eine Studie neuer facettendefinierender Ungleichungen präsentiert. Diese werden von den bekannten Knapsack Tree Ungleichungen abgeleitet. Wir untersuchen Verstärkungen basierend auf dem neuen Cluster Weight Polytop und zeigen polynomiale Separierungsalgorithmen für Spezialfälle. Die Duale der semidefiniten Relaxierung des Minumum Bisection Problems wird in ihrer äquivalenten Form als Eigenwertoptimierungsproblem mit dem Spektralen Bündelverfahren bearbeitet. Details der Implementierung bezüglich primaler Heuristiken, Branchingregeln, sogenannter Supporterweiterungen für die Schnittebenen und Warmstart werden präsentiert. Wir beenden die Arbeit mit einer numerischen Studie, in der wir zeigen, dass unser Zugang konkurrenzfähig zu aktuellen Implementationen basierend auf linearen und semidefiniten Relaxierungen ist.