SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering

Veronica Piccialli (), Antonio M. Sudoso () and Angelika Wiegele ()
Additional contact information
Veronica Piccialli: University of Rome Tor Vergata, 00133 Roma RM, Italy
Antonio M. Sudoso: University of Rome Tor Vergata, 00133 Roma RM, Italy
Angelika Wiegele: Universität Klagenfurt, 9020 Klagenfurt, Austria

INFORMS Journal on Computing, 2022, vol. 34, issue 4, 2144-2162

Abstract: The minimum sum-of-squares clustering problem (MSSC) consists of partitioning n observations into k clusters in order to minimize the sum of squared distances from the points to the centroid of their cluster. In this paper, we propose an exact algorithm for the MSSC problem based on the branch-and-bound technique. The lower bound is computed by using a cutting-plane procedure in which valid inequalities are iteratively added to the Peng–Wei semidefinite programming (SDP) relaxation. The upper bound is computed with the constrained version of k -means in which the initial centroids are extracted from the solution of the SDP relaxation. In the branch-and-bound procedure, we incorporate instance-level must-link and cannot-link constraints to express knowledge about which data points should or should not be grouped together. We manage to reduce the size of the problem at each level, preserving the structure of the SDP problem itself. To the best of our knowledge, the obtained results show that the approach allows us to successfully solve, for the first time, real-world instances up to 4,000 data points.

Keywords: clustering; semidefinite programming; branch and bound (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1166 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:4:p:2144-2162

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().