Daniel Aloise
and Pierre Hansen
Article (2009)
 Open Acess document in PolyPublie and at official publisher |
|
Open Access to the full text of this document Terms of Use: Creative Commons Attribution Non-commercial Download (230kB) |
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: | 01 Oct 2024 20:26 |
| 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 |
