# A Scalable Global Optimization Algorithm For Constrained Clustering

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 47 references that are in the map.
- First posted on arXiv 26 Oct 2025.

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

- [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)
- [An algorithm for clustering with confidence-based must-link and cannot-link constraints](https://mlsanity.com/paper/2212.14437/) (2022)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)

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

- [PASS: Certified Subset Repair for Classical and Quantum Pairwise Constrained Clustering](https://mlsanity.com/paper/2601.20157/) (2026)

## Abstract (arXiv)

Constrained clustering leverages limited domain knowledge to improve clustering performance and interpretability, but incorporating pairwise must-link and cannot-link constraints is an NP-hard challenge, making global optimization intractable. Existing mixed-integer optimization methods are confined to small-scale datasets, limiting their utility. We propose Sample-Driven Constrained Group-Based Branch-and-Bound (SDC-GBB), a decomposable branch-and-bound (BB) framework that collapses must-linked samples into centroid-based pseudo-samples and prunes cannot-link through geometric rules, while preserving convergence and guaranteeing global optimality. By integrating grouped-sample Lagrangian decomposition and geometric elimination rules for efficient lower and upper bounds, the algorithm attains highly scalable pairwise k-Means constrained clustering via parallelism. Experimental results show that our approach handles datasets with 200,000 samples with cannot-link constraints and 1,500,000 samples with must-link constraints, which is 200 - 1500 times larger than the current state-of-the-art under comparable constraint settings, while reaching an optimality gap of less than 3%. In providing deterministic global guarantees, our method also avoids the search failures that off-the-shelf heuristics often encounter on large datasets.