# Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming

arXiv: https://arxiv.org/abs/2209.08901 · HTML: https://mlsanity.com/paper/2209.08901/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 77 references that are in the map.
- First posted on arXiv 19 Sep 2022.

## Builds on (most cited first, 15 of 15)

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [A machine learning approach for forecasting hierarchical time series](https://mlsanity.com/paper/2006.00630/) (2020)
- [SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints](https://mlsanity.com/paper/1406.0942/) (2014)
- [On semidefinite relaxations for the block model](https://mlsanity.com/paper/1406.5647/) (2014)
- [Relax, no need to round: integrality of clustering formulations](https://mlsanity.com/paper/1408.4045/) (2014)
- [SOS-SDP: an Exact Solver for Minimum Sum-of-Squares Clustering](https://mlsanity.com/paper/2104.11542/) (2021)
- [An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering](https://mlsanity.com/paper/2111.15571/) (2021)
- [SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)](https://mlsanity.com/paper/1710.10604/) (2017)
- [Probably certifiably correct k-means clustering](https://mlsanity.com/paper/1509.07983/) (2015)
- [When Do Birds of a Feather Flock Together? k-Means, Proximity, and Conic Programming](https://mlsanity.com/paper/1710.06008/) (2017)
- [The ratio-cut polytope and K-means clustering](https://mlsanity.com/paper/2006.15225/) (2020)
- [Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization](https://mlsanity.com/paper/1705.07837/) (2017)
- [A Convergent 3-Block Semi-Proximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type of Constraints](https://mlsanity.com/paper/1404.5378/) (2014)
- [Improving ADMMs for Solving Doubly Nonnegative Programs through Dual Factorization](https://mlsanity.com/paper/1912.09851/) (2019)
- [Mixed-Integer Nonlinear Programming for State-based Non-Intrusive Load Monitoring](https://mlsanity.com/paper/2106.09158/) (2021)

## Built on by (most cited first, 3 of 3)

- [A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering](https://mlsanity.com/paper/2403.11351/) (2024)
- [Strong bounds for large-scale Minimum Sum-of-Squares Clustering](https://mlsanity.com/paper/2502.08397/) (2025)
- [Exact and Heuristic Algorithms for Constrained Biclustering](https://mlsanity.com/paper/2508.05493/) (2025)

## Abstract (arXiv)

The minimum sum-of-squares clustering (MSSC), or k-means type clustering, has been recently extended to exploit prior knowledge on the cardinality of each cluster. Such knowledge is used to increase performance as well as solution quality. In this paper, we propose a global optimization approach based on the branch-and-cut technique to solve the cardinality-constrained MSSC. For the lower bound routine, we use the semidefinite programming (SDP) relaxation recently proposed by Rujeerapaiboon et al. [SIAM J. Optim. 29(2), 1211-1239, (2019)]. However, this relaxation can be used in a branch-and-cut method only for small-size instances. Therefore, we derive a new SDP relaxation that scales better with the instance size and the number of clusters. In both cases, we strengthen the bound by adding polyhedral cuts. Benefiting from a tailored branching strategy which enforces pairwise constraints, we reduce the complexity of the problems arising in the children nodes. For the upper bound, instead, we present a local search procedure that exploits the solution of the SDP relaxation solved at each node. Computational results show that the proposed algorithm globally solves, for the first time, real-world instances of size 10 times larger than those solved by state-of-the-art exact methods.