A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem

Beitrag in einer Fachzeitschrift
(Originalarbeit)


Details zur Publikation

Autorinnen und Autoren: Ghaddar B, Anjos M, Liers F
Zeitschrift: Annals of Operations Research
Verlag: Springer Verlag (Germany)
Jahr der Veröffentlichung: 2011
Band: 188
Heftnummer: 1
Seitenbereich: 155-174
ISSN: 0254-5330


Abstract


The minimum k-partition (MkP) problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in the same partition. The main contribution of this paper is the design and implementation of a branch-and-cut algorithm based on semidefinite programming (SBC) for the MkP problem. The two key ingredients for this algorithm are: the combination of semidefinite programming with polyhedral results; and a novel iterative clustering heuristic (ICH) that finds feasible solutions for the MkP problem. We compare ICH to the hyperplane rounding techniques of Goemans and Williamson and of Frieze and Jerrum, and the computational results support the conclusion that ICH consistently provides better feasible solutions for the MkP problem. ICH is used in our SBC algorithm to provide feasible solutions at each node of the branch-and-bound tree. The SBC algorithm computes globally optimal solutions for dense graphs with up to 60 vertices, for grid graphs with up to 100 vertices, and for different values of k, providing a fast exact approach for k≥3. © 2008 Springer Science+Business Media, LLC.



FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

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


Einrichtungen weiterer Autorinnen und Autoren

University of Waterloo (UW)


Zitierweisen

APA:
Ghaddar, B., Anjos, M., & Liers, F. (2011). A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem. Annals of Operations Research, 188(1), 155-174. https://dx.doi.org/10.1007/s10479-008-0481-4

MLA:
Ghaddar, Bissan, Miguel Anjos, and Frauke Liers. "A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem." Annals of Operations Research 188.1 (2011): 155-174.

BibTeX: 

Zuletzt aktualisiert 2018-22-10 um 14:53