Exact Hyper-Rectangular Clustering via Adaptive Subset Selection

Abstract

We study the hyper-rectangular clustering problem (HRCP), where the goal is to partition a set of points into a fixed number of axis-aligned clusters while minimizing the total span. Existing exact approaches, based on mathematical optimization formulations, are limited to relatively small instances due to their strong dependence on the number of data points. We propose an incremental exact algorithm that exploits a key structural property of the problem: optimal cluster boundaries are determined by a subset of points, while interior points do not affect the objective value. The algorithm iteratively solves HRCP on carefully selected subsets of points and expands them only when necessary. A simple optimality condition ensures that, once a solution covers the entire dataset, it is optimal for the original problem. We introduce sampling strategies designed to identify points likely to lie on cluster boundaries, guiding the incremental process toward informative subsets. Computational experiments show that the proposed approach significantly improves scalability, solving instances with up to 10,000 points and substantially outperforming monolithic formulations.

Submitted to EJOR