<  Back to the Polytechnique Montréal portal

A branch-and-cut SDP-based algorithm for minimum sum-of-squares clustering

Daniel Aloise and Pierre Hansen

Article (2009)

Open Acess document in PolyPublie and at official publisher
[img]
Preview
Open Access to the full text of this document
Terms of Use: Creative Commons Attribution Non-commercial
Download (230kB)
Show abstract
Hide abstract

Abstract

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 & Xia (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.

Uncontrolled Keywords

clustering; sum-of-squares; semidefinite programming

Department: Department of Mathematics and Industrial Engineering
Research Center: GERAD - Research Group in Decision Analysis
Funders: CAPES/Brazil, Fonds de recherche du Québec - Nature et technologies (FRQNT), CRSNG / NSERC, HEC Montreal - Data Mining Chair
Grant number: 2479-04-4, 2007-PR-112176, 105574-07
PolyPublie URL: https://publications.polymtl.ca/55190/
Journal Title: Pesquisa Operacional (vol. 29, no. 3)
Publisher: SciELO
DOI: 10.1590/s0101-74382009000300002
Official URL: https://doi.org/10.1590/s0101-74382009000300002
Date Deposited: 18 Sep 2023 10:06
Last Modified: 10 Apr 2024 15:47
Cite in APA 7: Aloise, D., & Hansen, P. (2009). A branch-and-cut SDP-based algorithm for minimum sum-of-squares clustering. Pesquisa Operacional, 29(3), 503-516. https://doi.org/10.1590/s0101-74382009000300002

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Dimensions

Repository Staff Only

View Item View Item