Scalable and Globally Optimal Generalized L₁ K-center Clustering via Constraint Generation in Mixed Integer Linear Programming

Aravinth Chembu, Scott Sanner, Hassan Khurram, Akshat Kumar

Clustering is a cornerstone of unsupervised learning, yet traditional methods like $k$-means often struggle with imbalanced data where cluster densities vary significantly. The $k$-center problem addresses this by minimizing the maximum distance between any data point and its nearest center (a "minimax" objective), making it robust to class imbalance. However, the problem is NP-hard, and finding globally optimal solutions has historically been limited to small datasets of a few thousand points.

Presented at AAAI-23, this research introduces kc-Opt, the first algorithm capable of finding globally optimal solutions for generalized $L_1$ $k$-center clustering on datasets with up to one million points.

The kc-Opt Framework

The kc-Opt algorithm overcomes the computational barriers of exact clustering through three primary innovations:

  1. Generalized $L_1$ Formulation: By adopting the $L_1$ (Manhattan) distance, the authors formulate the clustering objective as a Mixed Integer Linear Program (MILP). Unlike $L_2$ (Euclidean) formulations, which lead to harder quadratic programs, the linear nature of $L_1$ allows the use of highly optimized commercial solvers like Gurobi.
  2. Constraint Generation: A standard MILP for $N$ points requires $N \times K$ constraints, which is intractable for large $N$. kc-Opt utilizes an iterative approach: it starts with a small subset of points, solves the MILP, identifies the most "violated" points (those furthest from current centers) in the full dataset, and adds them as new constraints. This process repeats until global optimality is reached.
  3. Outlier Robustness (kc-OptOut): Standard $k$-center clustering is highly sensitive to noise. The authors extended their MILP to allow $l$ points to remain unassigned, effectively ignoring outliers during optimization.
The iterative constraint generation process starts with a small subset of points to define initial centers.

Key Insights: The Boundary Advantage

A critical insight of this work is that the optimal centers in $k$-center clustering are determined solely by the "extreme" points on the boundaries of clusters. Points located in the cluster interior do not influence the final radius. This "boundary insight" explains why kc-Opt can solve a million-point problem while only ever processing a few hundred constraints at a time. For a synthetic dataset of 1,000,000 points, the algorithm reached the global optimum using only approximately 450 generated constraints.

Experimental Results

The authors evaluated kc-Opt against popular greedy baselines, such as Gonzalez’s algorithm (kc-Gon) and Hochbaum-Shmoys (kc-HS), across 20 real-world benchmark datasets (e.g., Iris, Adult, Skinsegment) and large-scale synthetic data.

Comparison of clustering results: (a) Gonzalez's greedy algorithm, (b) Hochbaum-Shmoys, and (c) the proposed optimal algorithm. The optimal algorithm finds centers that better minimize the maximum radius.

Performance Highlights:

  • Superior Accuracy: In many real-world cases, greedy approximations yielded objective values nearly double the true optimum found by kc-Opt.
  • Unprecedented Scale: The algorithm successfully optimized a synthetic dataset of 1,000,000 points across 15 clusters, a feat previously impossible for exact solvers.
  • Noise Handling: The kc-OptOut variant demonstrated the ability to recover ground-truth cluster centers even in heavily contaminated datasets, where standard algorithms were significantly skewed by outliers.

Conclusion and Future Directions

kc-Opt demonstrates that global optimality in $k$-center clustering is achievable at scale by combining MILP with constraint generation. While currently optimized for $L_1$ distance, future work may explore extending these techniques to $L_2$ distance via Mixed-Integer Quadratically Constrained Programming (MIQCP) or developing automated methods for estimating the optimal number of outliers ($l$).

Summary updated

Abstract

The k-center clustering algorithm, introduced over 35 years ago, is known to be robust to class imbalance prevalent in many clustering problems and has various applications such as data summarization, document clustering, and facility location determination. Unfortunately, existing k-center algorithms provide highly suboptimal solutions that can limit their practical application, reproducibility, and clustering quality. In this paper, we provide a novel scalable and globally optimal solution to a popular variant of the k-center problem known as generalized L_1 k-center clustering that uses L_1 distance and allows the selection of arbitrary vectors as cluster centers. We show that this clustering objective can be reduced to a mixed-integer linear program (MILP) that facilitates globally optimal clustering solutions. However, solving such a MILP may be intractable for large datasets; to remedy this, we present a scalable algorithm that leverages constraint generation to efficiently and provably converge to its global optimum. We further enhance outlier handling through a simple but elegant extension to our MILP objective. We first evaluate our algorithm on a variety of synthetic datasets to better understand its properties and then validate on 20 real benchmark datasets where we compare its performance to both traditional L_1 distance k-center and k-medians baselines. Our results demonstrate significant suboptimality of existing algorithms in comparison to our approach and further demonstrate that we can find optimal generalized L_1 k-center clustering solutions up to an unprecedented 1,000,000 data points.
BibTeX
@inproceedings{chembu2023scalable,
  author = {Aravinth Chembu and Scott Sanner and Hassan Khurram and Akshat Kumar},
  title = {{Scalable and Globally Optimal Generalized L₁ K-center Clustering via Constraint Generation in Mixed Integer Linear Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i6.25857},
}
Figure