Improved Decision Rule Approximations for Multistage Robust Optimization via Copositive Programming

We study decision rule approximations for generic multistage robust linear optimization problems. We examine linear decision rules for the case when the objective coefficients, the recourse matrices, and the right-hand sides are uncertain, and we explore quadratic decision rules for the case when only the right-hand sides are uncertain. The resulting optimization problems are NP hard but amenable to copositive programming reformulations that give rise to tight, tractable semidefinite programming solution approaches. We further enhance these approximations through new piecewise decision rule schemes. Finally, we prove that our proposed approximations are tighter than the state-of-the-art schemes and demonstrate their superiority through numerical experiments.

Funding: G. A. Hanasusanto was supported by the National Science Foundation [Grants 1752125 and 2153606].

Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2018.0505.