Back

G-2008-40

A Branch-and-Cut SDP-Based Algorithm for Minimum Sum-of-Squares Clustering

and

BibTeX reference

Minimum sum-of-squares clustering (MSSC) consists in partitioning a given set of n points into k clusters in order to minimize the sum of squared distances from the points to the centroid of their cluster. Recently, Peng and Xia (StudFuzz, 2005) established the equivalence between 0-1 semidefinite programming (SDP) and MSSC. In this paper, we propose a branch-and-cut algorithm for the underlying 0-1 SDP model. The algorithm obtains exact solutions for fairly large data sets with computing times comparable with those of the best exact method found in the literature.

, 16 pages

Research Axis

Research application

Publication

A branch-and-cut SDP-based algorithm for minimum sum-of-squares clustering
and
Pesquisa Operacional, 29, 503–516, 2009 BibTeX reference