Solving Minimum k-Partition Problems Using Semidefinite Programming

Miguel F. Anjos

Department of Management Sciences

University of Waterloo, Canada

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.

We present 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. 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 the best exact approach to date

for 3 or more partitions.

This is joint work with Bissan Ghaddar (Waterloo) and Frauke Liers

(Cologne).