A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization

• 成果类型: Article
• 署名作者: Bertsimas, Dimitris; Goyal, Vineet; Lu, Brian Y.
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Columbia University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0768-y
• 发表日期: 2015
• 页码: 281-319
• 关键词: stochastic-programming problems; Combinatorial Optimization; Adaptive optimization; convex-optimization; uncertainty; complexity; POWER

摘要

In this paper, we study the performance of static solutions for two-stage adjustable robust linear optimization problems with uncertain constraint and objective coefficients and give a tight characterization of the adaptivity gap. Computing an optimal adjustable robust optimization problem is often intractable since it requires to compute a solution for all possible realizations of uncertain parameters (Feige et al. in Lect Notes Comput Sci 4513:439-453, 2007). On the other hand, a static solution is a single (here and now) solution that is feasible for all possible realizations of the uncertain parameters and can be computed efficiently for most dynamic optimization problems. We show that for a fairly general class of uncertainty sets, a static solution is optimal for the two-stage adjustable robust linear packing problems. This is highly surprising in view of the usual perception about the conservativeness of static solutions. Furthermore, when a static solution is not optimal for the adjustable robust problem, we give a tight approximation bound on the performance of the static solution that is related to a measure of non-convexity of a transformation of the uncertainty set. We also show that our bound is at least as good (and in many case significantly better) as the bound given by the symmetry of the uncertainty set (Bertsimas and Goyal in Math Methods Oper Res 77(3):323-343, 2013; Bertsimas et al. in Math Oper Res 36(1):24-54, 2011).