Branch-and-Cut for an SDP Relaxation of Large-Scale Minimum Bisection Problems

Name: Branch-and-Cut for an SDP Relaxation of Large-Scale Minimum Bisection Problems
Brand: VDM Verlag Dr. Mueller E.K.
SKU: 9783836486903
Price: 68.3 EUR
Availability: InStock

Autor: Michael Armbruster

Jazyk:

Väzba: Brožovaná

Vydavateľ: VDM Verlag Dr. Mueller E.K.

Dostupnosť: Skladom u dodávateľa

Odosielame za 8-11 dní

68.30 €

The minimum bisection problem (MB) is a challenging graph partitioning problem with numerous applica...

Informácie o knihe

Autor

Michael Armbruster

Jazyk

Angličtina

Väzba

Kniha - Brožovaná

Vydalo

2008

Stránok

240

EAN

9783836486903

ISBN

3836486903

Enbook ID

06861308

Vydavateľ

VDM Verlag Dr. Mueller E.K.

Hmotnosť

327

Rozmery

152 x 229 x 13

Kompletný popis

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

Mohlo by vás zaujímať

Zákazníci, ktorí si kúpili túto knihu, kúpili tiež

Najčastejšie vyhľadávané

Categories

Authors

Publishers

Produkty

Produkty

Najčastejšie vyhľadávané

Categories

Authors

Publishers

Produkty

Produkty

Branch-and-Cut for an SDP Relaxation of Large-Scale Minimum Bisection Problems

Informácie o knihe

Kompletný popis

Mohlo by vás zaujímať

Zákazníci, ktorí si kúpili túto knihu, kúpili tiež