Designing Tractable Piecewise Affine Policies for Multi-Stage Adjustable Robust Optimization
From MaRDI portal
Publication:6507882
DOI10.1007/S10107-023-02053-0arXiv2207.00403WikidataQ128608356 ScholiaQ128608356MaRDI QIDQ6507882FDOQ6507882
Authors: Simon Thomä, Grit Walther, Maximilian Schiffer 
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 when uncertainty is replaced by these new sets. We then demonstrate how solutions for this alternative problem can be transformed to 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. In two numerical experiments we identify beneficial and disadvantageous properties for our policies and present effective adjustments to tackle the most critical disadvantages. 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.
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Minimax problems in mathematical programming (90C47) Optimality conditions for minimax problems (49K35)
This page was built for publication: Designing Tractable Piecewise Affine Policies for Multi-Stage Adjustable Robust Optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6507882)
