In this paper, we study adaptive robust optimization problems with discrete uncertainty. We first show that an adaptive robust counterpart of the multiple knapsack problem includes $\Sigma_2^P$-hard problems. Then, we theoretically prove the validity of a non-trivial reformulation of this class of problems which can be solved by an enumerative algorithm akin to a Branch-and-Benders-cut scheme. Our reformulation shows that, for discrete uncertainty sets, adaptive robust problems with uncertain constraints can equivalently be solved as problems with objective uncertainty only. Unlike most of the existing literature, our approach is not restricted to continuous wait-and-see decisions. We then show some experimental results on the robust counterpart of the multiple knapsack problem.
Citation
Lefebvre, H., Malaguti, E. & Monaci, M., (2021) Adaptive robust optimization with discrete uncertainty