Designing tractable piecewise affine policies for multi-stage adjustable robust optimization
Mathematical Programming, vol. 208, pp. 661–716
Abstract
Abstract We study piecewise affine policies for multi-stage adjustable robust optimization (ARO) problems with non-negative right-hand side uncertainty. First, we construct new dominating uncertainty sets and show how a multi-stage ARO problem can be solved efficiently with a linear program when uncertainty is replaced by these new sets. We then demonstrate how solutions for this alternative problem can be transformed into solutions for the original problem. By carefully choosing the dominating sets, we prove strong approximation bounds for our policies and extend many previously best-known bounds for the two-staged problem variant to its multi-stage counterpart. Moreover, the new bounds are—to the best of our knowledge—the first bounds shown for the general multi-stage ARO problem considered. We extensively compare our policies to other policies from the literature and prove relative performance guarantees. In two numerical experiments, we identify beneficial and disadvantageous properties for different policies and present effective adjustments to tackle the most critical disadvantages of our policies. Overall, the experiments show that our piecewise affine policies can be computed by orders of magnitude faster than affine policies, while often yielding comparable or even better results.
Authors 3
-
Affiliation as printed
Chair of Operations Management, RWTH Aachen University, Aachen, Germany
-
Affiliation as printed
Chair of Operations Management, RWTH Aachen University, Aachen, Germany
-
Maximilian Schiffer corresponding
Technical University of Munich
Affiliation as printed
School of Management and Munich Data Science Institute, Technical University of Munich, Munich, Germany
Cited by 13 stored of 14
13 results
No patents citing this paper on Lens.org (checked 2026-10-06).