Solving k-way graph partitioning problems to optimality: The impact of semidefinite relaxations and the bundle method

Beitrag in einem Sammelwerk
(Originalarbeit)


Details zur Publikation

Autorinnen und Autoren: Anjos M, Ghaddar B, Hupp LM, Liers F, Wiegele A
Herausgeber: Michael Jünger, Gerhard Reinelt
Titel Sammelwerk: Facets of Combinatorial Optimization
Verlag: Springer-Verlag Berlin Heidelberg
Jahr der Veröffentlichung: 2013
Band: 9783642381898
Seitenbereich: 355-386
ISBN: 9783642381881


Abstract


This paper is concerned with computing global optimal solutions for maximum k-cut problems. We improve on the SBC algorithm of Ghaddar, Anjos and Liers in order to compute such solutions in less time. We extend the design principles of the successful BiqMac solver for maximum 2-cut to the general maximum k-cut problem. As part of this extension, we investigate different ways of choosing variables for branching. We also study the impact of the separation of clique inequalities within this new framework and observe that it frequently reduces the number of subproblems considerably. Our computational results suggest that the proposed approach achieves a drastic speedup in comparison to SBC, especially when k=3. We also made a comparison with the orbitopal fixing approach of Kaibel, Peinhardt and Pfetsch. The results suggest that, while their performance is better for sparse instances and larger values of k, our proposed approach is superior for smaller k and for dense instances of medium size. Furthermore, we used CPLEX for solving the ILP formulation underlying the orbitopal fixing algorithm and conclude that especially on dense instances the new algorithm outperforms CPLEX by far.



FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Hupp, Lena
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)
Liers-Bergmann, Frauke Prof. Dr.
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)


Einrichtungen weiterer Autorinnen und Autoren

Alpen-Adria-Universität Klagenfurt
University of Waterloo (UW)


Zitierweisen

APA:
Anjos, M., Ghaddar, B., Hupp, L.M., Liers, F., & Wiegele, A. (2013). Solving k-way graph partitioning problems to optimality: The impact of semidefinite relaxations and the bundle method. In Michael Jünger, Gerhard Reinelt (Eds.), Facets of Combinatorial Optimization. (pp. 355-386). Springer-Verlag Berlin Heidelberg.

MLA:
Anjos, Miguel, et al. "Solving k-way graph partitioning problems to optimality: The impact of semidefinite relaxations and the bundle method." Facets of Combinatorial Optimization. Ed. Michael Jünger, Gerhard Reinelt, Springer-Verlag Berlin Heidelberg, 2013. 355-386.

BibTeX: 

Zuletzt aktualisiert 2018-17-10 um 21:53