Robust optimization is an approach for handling uncertainty in optimization problems, in which the uncertainty set determines the conservativeness of the solutions. In this paper, we propose a data-driven uncertainty set using a type of volume-based clustering, which we call Minimum-Volume Norm-Based Clustering (MVNBC). MVNBC extends the concept of minimum-volume ellipsoid clustering by allowing clusters to be enclosed within regions defined by a given set of vector norms, while explicitly detecting outliers at a specified rate. We formulate MVNBC as a mixed-integer conic optimization problem to optimally assign data points to clusters by minimizing the total volume of the norm-based regions. To address computational complexities, we develop both an exact decomposition-based algorithm and an efficient iterative approximation algorithm. The exact algorithm employs generalized Benders decomposition to decompose the problem into an assignment master problem and conic subproblems. The approximation algorithm, inspired by insights from generalized Benders decomposition, iteratively reassigns data points to different clusters until guaranteed convergence. Through extensive numerical experiments, we first show that MVNBC effectively captures data patterns and identifies clusters with minimum total volume. Moreover, we demonstrate that robust solutions derived from our uncertainty set are less conservative than those obtained using uncertainty sets without clustering or those obtained using selected benchmarks from the literature.
Citation
Yazdani, A., Marandi, A., Basten, R., & Tan, L. (2025). A Clustering-based uncertainty set for Robust Optimization. https://optimization-online.org/?p=26195