Exact Methods for Solving k-Delete Recoverable Robust 0-1 Problems Under Budgeted Uncertainty
Abstract
We study the k-delete recoverable robust 0-1 problem in which a decision-maker solves a combinatorial optimization problem subject to objective uncertainty. The model follows a two-stage robust setup. The decision-maker first commits to an initial plan and may then revoke up to k components of this decision after the uncertainty is revealed. The underlying uncertainty is modeled using a budgeted uncertainty set so that the decision-maker only hedges against a limited number of deviations in the uncertain parameters. We present four reformulations of the k-delete recoverable robust problem, which can be tackled using (i) general-purpose mixed-integer linear programming solvers, (ii) branch-and-cut methods, or (iii) column-and-constraint generation algorithms. For each formulation, we identify suitable solution methods and prove their correctness. Overall, we present eight approaches to solve the k-delete recoverable robust problem, which we assess and compare in an extensive computational study on instances of the assignment problem and the single-source capacitated facility location problem.
Related
- On randomized batch-sampling coordinate descent methods for solving linear least-squares problems
- Constructing Data-Driven Budgeted Uncertainty Sets for Robust Optimization
- Solving Inverse Dirac-weighted Sturm-Liouville Problems via Cauchy problems
- Solving Multiobjective Linear Set Optimization Problems
- Error Analysis for Solving Elliptic Interface Problems with Randomized Neural Networks
BibTeX
@misc{beck2026exact,
title = {{Exact Methods for Solving k-Delete Recoverable Robust 0-1 Problems Under Budgeted Uncertainty}},
author = {Yasmine Beck and Christina Büsing and Ivana Ljubić},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29478},
eprint = {2609.29478},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29478},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact Methods for Solving k-Delete Recoverable Robust 0-1 Problems Under Budgeted Uncertainty
AU - Yasmine Beck
AU - Christina Büsing
AU - Ivana Ljubić
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.29478
UR - https://arxiv.org/abs/2609.29478
AB - We study the k-delete recoverable robust 0-1 problem in which a decision-maker solves a combinatorial optimization problem subject to objective uncertainty. The model follows a two-stage robust setup. The decision-maker first commits to an initial plan and may then revoke up to k components of this decision after the uncertainty is revealed. The underlying uncertainty is modeled using a budgeted uncertainty set so that the decision-maker only hedges against a limited number of deviations in the uncertain parameters. We present four reformulations of the k-delete recoverable robust problem, which can be tackled using (i) general-purpose mixed-integer linear programming solvers, (ii) branch-and-cut methods, or (iii) column-and-constraint generation algorithms. For each formulation, we identify suitable solution methods and prove their correctness. Overall, we present eight approaches to solve the k-delete recoverable robust problem, which we assess and compare in an extensive computational study on instances of the assignment problem and the single-source capacitated facility location problem.
ER -