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.


Published in:
IEEE Conference on Decision and Control and European Control Conference, 7386-7391
Presented at:
2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC 2011), Orlando, FL, USA, 12-15 December 2011
Year:
2011
Publisher:
IEEE
ISBN:
978-1-61284-800-6
Keywords:
Laboratories:




 Record created 2014-01-29, last modified 2018-09-13

External link:
Download fulltext
URL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)