Retour

G-2008-40

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

et

référence BibTeX

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

Axe de recherche

Application de recherche

Publication

A branch-and-cut SDP-based algorithm for minimum sum-of-squares clustering
et
Pesquisa Operacional, 29, 503–516, 2009 référence BibTeX