Groupe d’études et de recherche en analyse des décisions

G-2012-50

Solving k-way Graph Partitioning Problems to Optimality: The Impact of Semidefinite Relaxations and the Bundle Method

, , , et

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. Our preliminary computational results suggest that the proposed approach achieves a drastic speedup in comparison to SBC. 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. Finally, a comparison with the results reported from the application of the orbitopal fixing technique suggests that our approach performs better than orbitopal fixing for k=3 and medium-sized dense instances with 30 nodes, whereas the latter's performance is better for larger values of k and for sparse instances defined on grids with Gaussian distributed edge weights.

, 21 pages