Constructing Data-Driven Budgeted Uncertainty Sets for Robust Optimization
Abstract
In robust optimization, budgeted uncertainty sets offer a popular trade-off between modeling flexibility and computational tractability. Data that is observed in practice is often discrete in nature, which creates the need for tools to construct budgeted uncertainty sets based on observed data. This paper presents a principled approach for this purpose, which ensures that any solution found through the robust problem with respect to the constructed budgeted uncertainty set offers an approximation guarantee with respect to the optimal value of the problem with discrete data. Our approach is purely based on the geometry of data and can be applied to any nominal optimization problem. We discuss the problem of evaluating budgeted uncertainty sets, and how to construct them using exact and heuristic methods. In computational experiments, we show that it is possible to construct sets with little computation time that offer guarantees that are close to optimality.
Related
- Exact Methods for Solving k-Delete Recoverable Robust 0-1 Problems Under Budgeted Uncertainty
- Adjustable Robust Optimization with Discrete Uncertainty
- Robust Optimization Under Objective Functional Uncertainty
- Robust Resource Management for SAGIN using DNN-Driven Channel Uncertainty Learning
- Data-driven joint optimization of maintenance and spare parts provisioning: A distributionally robust approach
BibTeX
@misc{fairbrother2026constructing,
title = {{Constructing Data-Driven Budgeted Uncertainty Sets for Robust Optimization}},
author = {Jamie Fairbrother and Marc Goerigk and Qiongyan Zeng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37537},
eprint = {2610.37537},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.37537},
}
RIS
TY - UNPB
TI - Constructing Data-Driven Budgeted Uncertainty Sets for Robust Optimization
AU - Jamie Fairbrother
AU - Marc Goerigk
AU - Qiongyan Zeng
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.37537
UR - https://arxiv.org/abs/2610.37537
AB - In robust optimization, budgeted uncertainty sets offer a popular trade-off between modeling flexibility and computational tractability. Data that is observed in practice is often discrete in nature, which creates the need for tools to construct budgeted uncertainty sets based on observed data. This paper presents a principled approach for this purpose, which ensures that any solution found through the robust problem with respect to the constructed budgeted uncertainty set offers an approximation guarantee with respect to the optimal value of the problem with discrete data. Our approach is purely based on the geometry of data and can be applied to any nominal optimization problem. We discuss the problem of evaluating budgeted uncertainty sets, and how to construct them using exact and heuristic methods. In computational experiments, we show that it is possible to construct sets with little computation time that offer guarantees that are close to optimality.
ER -