Optimization Online


A Branch-and-Cut Algorithm based on Semidefinite Programming for the Minimum k-Partition Problem

Bissan Ghaddar (bghaddar***at***uwaterloo.ca)
Miguel Anjos (manjos***at***uwaterloo.ca)
Frauke Liers (liers***at***informatik.uni-koeln.de)

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 (SDP) with polyhedral results; and the 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. 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 the best exact approach to date for k>2.

Keywords: semidefinite programming, branch-and-cut, polyhedral cuts

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Published in Annals of Operations Research, 2008. DOI: 10.1007/s10479-008-0481-4


Entry Submitted: 07/31/2007
Entry Accepted: 07/31/2007
Entry Last Modified: 09/09/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society