-
Nemecký jazyk
Branch-and-Cut for an SDP Relaxation of Large-Scale Minimum Bisection Problems
Autor: Michael Armbruster
The minimum bisection problem (MB) is a challenging graph partitioning problem with numerous applications. Several inexact solution approaches for MB showed up in recent years. For the exact solution of large instances of MB, linear programming (LP) based... Viac o knihe
Na objednávku, dodanie 2-4 týždne
73.17 €
bežná cena: 81.30 €
O knihe
The minimum bisection problem (MB) is a challenging graph partitioning problem with numerous applications. Several inexact solution approaches for MB showed up in recent years. For the exact solution of large instances of MB, linear programming (LP) based methods were dominating. This doctoral thesis deals with the exact solution of large-scale MB via a semidefinite programming (SDP) relaxation in a branch-and-cut framework. After reviewing known results on the underlying bisection cut polytope, new valid inequalities are studied. Strengthenings based on the new cluster weight polytope and polynomial separation algorithms for special cases are investigated. Computationally, the dual of the SDP relaxation of MB is tackled in its equivalent form as an eigenvalue optimisation problem with the spectral bundle method. Details of the implementation are presented, including primal heuristics, branching rules, support extensions and warm start. A study showing that the chosen approach is competitive to state-of-the-art implementations using LP or SDP relaxations concludes the thesis. The book is aimed at researchers and practitioners in optimisation and discrete mathematics.
- Vydavateľstvo: VDM Verlag Dr. Müller e.K.
- Rok vydania: 2013
- Formát: Paperback
- Rozmer: 220 x 150 mm
- Jazyk: Nemecký jazyk
- ISBN: 9783836486903
Anglický jazyk 
