# An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 76 references that are in the map.
- First posted on arXiv 30 Nov 2021.

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

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [A Framework for Deep Constrained Clustering -- Algorithms and Advances](https://mlsanity.com/paper/1901.10061/) (2019)
- [SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints](https://mlsanity.com/paper/1406.0942/) (2014)
- [Optimization Problems for Machine Learning: A Survey](https://mlsanity.com/paper/1901.05331/) (2019)
- [SOS-SDP: an Exact Solver for Minimum Sum-of-Squares Clustering](https://mlsanity.com/paper/2104.11542/) (2021)
- [SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)](https://mlsanity.com/paper/1710.10604/) (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)

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

- [An algorithm for clustering with confidence-based must-link and cannot-link constraints](https://mlsanity.com/paper/2212.14437/) (2022)
- [Global k-means++: an effective relaxation of the global k-means clustering algorithm](https://mlsanity.com/paper/2211.12271/) (2022)
- [Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming](https://mlsanity.com/paper/2209.08901/) (2022)
- [A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering](https://mlsanity.com/paper/2403.11351/) (2024)
- [Predicting municipalities in financial distress: a machine learning approach enhanced by domain expertise](https://mlsanity.com/paper/2302.05780/) (2023)
- [Strong bounds for large-scale Minimum Sum-of-Squares Clustering](https://mlsanity.com/paper/2502.08397/) (2025)
- [A Scalable Global Optimization Algorithm For Constrained Clustering](https://mlsanity.com/paper/2510.22519/) (2025)
- [Memetic Differential Evolution Methods for Semi-Supervised Clustering](https://mlsanity.com/paper/2403.04322/) (2024)
- [Fair Clustering with Minimum Representation Constraints](https://mlsanity.com/paper/2409.02963/) (2024)
- [Exact and Heuristic Algorithms for Constrained Biclustering](https://mlsanity.com/paper/2508.05493/) (2025)
- [PASS: Certified Subset Repair for Classical and Quantum Pairwise Constrained Clustering](https://mlsanity.com/paper/2601.20157/) (2026)
- [Kempe Swap K-Means: A Scalable Near-Optimal Solution for Semi-Supervised Clustering](https://mlsanity.com/paper/2603.27417/) (2026)
- [An Algebraic Approach to Constrained K-means Clustering](https://mlsanity.com/paper/2610.14932/) (2026)

## Abstract (arXiv)

The minimum sum-of-squares clustering (MSSC), or k-means type clustering, is traditionally considered an unsupervised learning task. In recent years, the use of background knowledge to improve the cluster quality and promote interpretability of the clustering process has become a hot research topic at the intersection of mathematical optimization and machine learning research. The problem of taking advantage of background information in data clustering is called semi-supervised or constrained clustering. In this paper, we present a branch-and-cut algorithm for semi-supervised MSSC, where background knowledge is incorporated as pairwise must-link and cannot-link constraints. For the lower bound procedure, we solve the semidefinite programming relaxation of the MSSC discrete optimization model, and we use a cutting-plane procedure for strengthening the bound. For the upper bound, instead, by using integer programming tools, we use an adaptation of the k-means algorithm to the constrained case. For the first time, the proposed global optimization algorithm efficiently manages to solve real-world instances up to 800 data points with different combinations of must-link and cannot-link constraints and with a generic number of features. This problem size is about four times larger than the one of the instances solved by state-of-the-art exact algorithms.