# Neural Capacitated Clustering

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 67 references that are in the map.
- First posted on arXiv 10 Feb 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Unsupervised Deep Embedding for Clustering Analysis](https://mlsanity.com/paper/1511.06335/) (2015)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Towards K-means-friendly Spaces: Simultaneous Deep Learning and Clustering](https://mlsanity.com/paper/1610.04794/) (2016)
- [Deep Clustering: A Comprehensive Survey](https://mlsanity.com/paper/2210.04142/) (2022)
- [Differentiable Deep Clustering with Cluster Size Constraints](https://mlsanity.com/paper/1910.09036/) (2019)
- [A Framework for Deep Constrained Clustering](https://mlsanity.com/paper/2101.02792/) (2021)
- [Deep Conditional Gaussian Mixture Model for Constrained Clustering](https://mlsanity.com/paper/2106.06385/) (2021)
- [Edge computing server placement with capacitated location allocation](https://mlsanity.com/paper/1907.07349/) (2019)

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

- [Too Big, so Fail? -- Enabling Neural Construction Methods to Solve Large-Scale Routing Problems](https://mlsanity.com/paper/2309.17089/) (2023)
- [Neural Cluster First, Route Second: Capacitated Vehicle Routing via Differentiable Optimal Transport](https://mlsanity.com/paper/2605.09301/) (2026)

## Abstract (arXiv)

Recent work on deep clustering has found new promising methods also for constrained clustering problems. Their typically pairwise constraints often can be used to guide the partitioning of the data. Many problems however, feature cluster-level constraints, e.g. the Capacitated Clustering Problem (CCP), where each point has a weight and the total weight sum of all points in each cluster is bounded by a prescribed capacity. In this paper we propose a new method for the CCP, Neural Capacited Clustering, that learns a neural network to predict the assignment probabilities of points to cluster centers from a data set of optimal or near optimal past solutions of other problem instances. During inference, the resulting scores are then used in an iterative k-means like procedure to refine the assignment under capacity constraints. In our experiments on artificial data and two real world datasets our approach outperforms several state-of-the-art mathematical and heuristic solvers from the literature. Moreover, we apply our method in the context of a cluster-first-route-second approach to the Capacitated Vehicle Routing Problem (CVRP) and show competitive results on the well-known Uchoa benchmark.