Dipl.-Math. oec. Michael Armbruster

Branch-and-Cut for a Semidefinite Relaxation of Large-scale Minimum Bisection Problems

Dokumente und Dateien

Hinweis

Bitte nutzen Sie beim Zitieren immer folgende Url:

http://nbn-resolving.de/urn:nbn:de:swb:ch1-200701057

Kurzfassung in Englisch

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.

Kurzfassung in Deutsch

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.

weitere Metadaten

Schlagwörter
Cluster Weight Polytop
Schlagwörter
Kombinatorische Optimierung
SWD SchlagworteBisektionsproblem
SWD SchlagworteBranch-and-Cut-Methode
SWD SchlagworteSemidefinite Optimierung
DDC Klassifikation510
Institution(en) 
HochschuleTU Chemnitz
FakultätFakultät für Mathematik
BetreuerProf. Dr. Christoph Helmberg
GutachterProf. Dr. Christoph Helmberg
Prof. Dr. Alexander Martin
Prof. Dr. Franz Rendl
DokumententypDissertation
SpracheEnglisch
Tag d. Einreichung (bei der Fakultät)05.04.2007
Tag d. Verteidigung / Kolloquiums / Prüfung14.06.2007
Veröffentlichungsdatum (online)22.06.2007
persistente URNurn:nbn:de:swb:ch1-200701057

Hinweis zum Urheberrecht

Diese Website ist eine Installation von Qucosa - Quality Content of Saxony!
Sächsische Landesbibliothek Staats- und Universitätsbibliothek Dresden