Robust Optimization (RO) is an approach to tackle uncertainties in the parameters of an optimization problem. Constructing an uncertainty set is crucial for RO, as it determines the quality and the conservativeness of the solutions. In this paper, we introduce an approach for constructing a data-driven uncertainty set through volume-based clustering, which we call Minimum-Volume Norm-Based Clustering (MVNBC), that leads to less conservative solutions. MVNBC extends the concept of Minimum-Volume Ellipsoid Clustering by enabling customizable regions containing clusters. These regions are defined based on a given set of vector norms, hence providing great flexibility in capturing diverse data patterns. We formulate a mixed-integer conic optimization problem for MVNBC. To address computational complexities, we design an efficient iterative approximation algorithm where we reassign points to clusters and improve the volume of the regions. Our numerical experiments demonstrate the effectiveness of our approach in capturing data patterns and finding clusters with minimum total volume. Moreover, constructed uncertainty sets based on MVNBC result in robust solutions with 10% improvement in the objective value compared to the ones obtained by a recent data-driven uncertainty set. Therefore, using our uncertainty sets in RO problems can generate less conservative solutions compared to traditional uncertainty sets as well as other existing data-driven approaches.
Citation
Yazdani, A., Marandi, A., Basten, R., & Tan, L. (2024). A Clustering-based uncertainty set for Robust Optimization. https://optimization-online.org/?p=26195
Article
View A Clustering-based uncertainty set for Robust Optimization