When we task an algorithm with clustering a dataset, we are usually content with an approximation. Standard tools like the $k$-means heuristic (Lloyd's algorithm) are fast and find "good enough" local minima, but they offer no guarantees of finding the absolute best mathematical partition.
Finding the globally optimal solution to clustering problems—such as Minimum Sum-of-Squares Clustering (MSSC), $k$-medoids, or $k$-center—is notoriously NP-hard. The reason lies in a combinatorial trap: traditional exact algorithms try to solve clustering by branching on discrete assignment variables. For a dataset of $N$ samples and $K$ clusters, there are $K^N$ possible ways to assign points to clusters. If you attempt to navigate this space using a standard Branch-and-Bound (BB) tree, the tree's size explodes exponentially with the number of data points. Consequently, classic global solvers hit a hard wall at just a few hundred or thousands of samples.
A recent surge of research has broken through this barrier, scaling exact global optimization to datasets with millions—and even billions—of samples. The core insight behind this breakthrough is a paradigm shift known as reduced-space branching.
Shifting the Search Space from Points to Centers
To understand why reduced-space branching works, we have to look at the underlying geometry of a cluster. A clustering assignment is entirely dictated by the positions of its cluster centers. If you are given the exact coordinates of the $K$ optimal centers, finding the optimal assignment for the $N$ data points becomes trivial: you simply assign each point to its nearest center. This step takes polynomial time and can be done independently for each sample.
Instead of branching on the massive, discrete space of point assignments ($K^N$), what if we branch on the continuous spatial coordinates of the cluster centers?
Traditional Branching (Assignment Space):
Root ─── Point 1 in Cluster 1 ─── Point 2 in Cluster 1 ... (Explodes with N)
└─── Point 1 in Cluster 2 ─── Point 2 in Cluster 1 ...
Reduced-Space Branching (Center Space):
Root ─── Center 1 in Region A ─── Center 2 in Region C ... (Independent of N)
└─── Center 1 in Region B ─── Center 2 in Region C ...
In most practical applications, the number of clusters $K$ and the spatial dimensionality $d$ are small, while the number of data points $N$ is massive ($K, d \ll N$). By restricting the branching process to the continuous domain of cluster center locations, the depth and branching factor of the search tree become entirely decoupled from the total number of data points. The combinatorial explosion is dictated by $K$ and $d$, while $N$ is relegated to a sub-problem.
How the Decoupling Works
A global optimization framework like Branch-and-Bound requires two main operations: partitioning the search space (branching) and estimating the best possible score within a partition (bounding). Reduced-space branching executes these steps by treating the data points as a static background and the centers as moving targets:
- Branching on Regions: The algorithm begins with a bounding box that encompasses the entire dataset. It then systematically partitions this continuous space into smaller sub-regions (hyperrectangles or intervals) where potential cluster centers might reside.
- Isolating $N$ in the Bounding Phase: When the algorithm needs to calculate a lower bound for a specific node in the search tree, it doesn't look at individual point combinations. Instead, it calculates the minimum possible distance between each data point and the entire continuous region assigned to a cluster center.
Because the data points do not dictate the structure of the search tree, the computational workload involving $N$ is isolated within a highly efficient sub-problem. As Ryner et al. demonstrate in A cutting plane algorithm for globally solving low-dimensional k-means problems, this formulation allows the primary workload of processing millions of observations to be absorbed by a linear sub-problem, keeping the global optimization routine highly efficient.
Scaling Across Different Clustering Objectives
The beauty of reduced-space branching is its versatility across different mathematical formulations of clustering. By tailoring how the lower bounds are calculated within the center regions, researchers have shattered scaling records across several variants:
Minimum Sum-of-Squares ($k$-means)
In A Scalable Deterministic Global Optimization Algorithm for Clustering Problems, Hua et al. reformulated clustering as a two-stage optimization problem. By restricting branching operations exclusively to the cluster centers, they prevented the search tree from expanding exponentially, scaling deterministic global optimization to datasets with over 200,000 samples—a 100x improvement over prior exact solvers.
$K$-Medoids
Unlike $k$-means, $k$-medoids requires cluster centers to be actual data points from the dataset. Ren et al. adapted the reduced-space framework to this discrete variant in Global Optimal K-Medoids Clustering of One Million Samples. By partitioning the search space based on continuous bounding regions of the medoid centers and pairing it with a tailored Lagrangian relaxation technique, they achieved provably optimal solutions for up to one million samples.
$K$-Center
The $k$-center problem aims to minimize the maximum distance between any point and its closest center. In Global Optimization of K-Center Clustering, Shi et al. utilized a spatial branch-and-bound scheme on center coordinates to scale to 14 million samples. Building on this, Ren et al. introduced a specialized closed-form lower bound in A Global Optimization Algorithm for K-Center Clustering of One Billion Samples, successfully finding global optima for datasets containing up to one billion samples.
Constrained Clustering
Real-world clustering often comes with background knowledge or constraints (e.g., certain points must or must not be grouped together). Chumpitaz-Flores et al. brought the reduced-space philosophy to this domain with SDC-GBB in A Scalable Global Optimization Algorithm For Constrained Clustering. By navigating continuous cluster center coordinates and leveraging geometric pruning rules, they bypassed the combinatorial explosion of binary point assignments, scaling constrained exact clustering to millions of points.
The Core Algorithmic Lesson
The dramatic scaling achieved by these methods highlights a broader principle in algorithm design: when the size of your dataset ($N$) threatens to break your solver, look for a representation where the complexity depends on the problem's structural parameters ($K$ and $d$) instead.
This philosophy of decoupling bottlenecks also echoes in local search heuristics. For example, in LSDS++ : Dual Sampling for Accelerated k-means++, Fan et al. tackle a different scaling bottleneck—a high number of clusters $K$. By replacing exhaustive center evaluations with a dual sampling strategy during initialization, they made the local search refinement step independent of $K$.
Whether the goal is accelerating local seeding or finding a mathematically provable global optimum, the recipe for modern large-scale clustering remains the same: isolate the massive dimensions of your data, project the hard combinatorial choices into a reduced space, and let the structure of the problem do the heavy lifting.
Key Foundational Work
A Scalable Deterministic Global Optimization Algorithm for Clustering Problems (2021) — contributed 4 concept elements to this direction.
Global Optimization of K-Center Clustering (2022) — contributed 4 concept elements to this direction.
Global Optimal K-Medoids Clustering of One Million Samples (2022) — contributed 1 concept elements to this direction.