A scenario approach for estimating the suboptimality of linear decision rules in two-stage robust optimization

Robust dynamic optimization problems involving adaptive decisions are computationally intractable in general. Tractable upper bounding approximations can be obtained by requiring the adaptive decisions to be representable as linear decision rules (LDRs). In this paper we investigate families of tractable lower bounding approximations, which serve to estimate the degree of suboptimality of the best LDR. These approximations are obtained either by solving a dual version of the robust optimization problem in LDRs or by utilizing an inclusion-wise discrete approximation of the problem´s uncertainty set. The quality of the resulting lower bounds depends on the distribution assigned to the uncertain parameters or the choice of the discretization points within the uncertainty set, respectively. We prove that identifying the best possible lower bounds is generally intractable in both cases and propose an efficient procedure to construct suboptimal lower bounds. The resulting instance-wise bounds outperform known worst-case bounds in the majority of our test cases.