Universität zu Köln

Anjos, Miguel, Ghaddar, Bissan, Hupp, Lena, Liers, Frauke and Wiegele, Angelika ORCID: 0000-0003-1670-7951 (2013). Solving k-way Graph Partitioning Problems to Optimality: The Impact of Semidefinite Relaxations and the Bundle Method. In: Facets of Combinatorial Optimization : Festschrift for Martin Grötschel, pp. 355-386. Berlin: Springer.

Preview

PDF techrep.pdf - Draft Version Download (234kB) | Preview

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.

Item Type:	Book Section, Proceedings Item or annotation in a legal commentary
Creators:	Creators Email ORCID ORCID Put Code Anjos, Miguel UNSPECIFIED UNSPECIFIED UNSPECIFIED Ghaddar, Bissan UNSPECIFIED UNSPECIFIED UNSPECIFIED Hupp, Lena UNSPECIFIED UNSPECIFIED UNSPECIFIED Liers, Frauke UNSPECIFIED UNSPECIFIED UNSPECIFIED Wiegele, Angelika UNSPECIFIED orcid.org/0000-0003-1670-7951 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-550327
Title of Book:	Facets of Combinatorial Optimization : Festschrift for Martin Grötschel
Page Range:	pp. 355-386
Date:	2013
Publisher:	Springer
Place of Publication:	Berlin
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/55032