On the performance of affine policies for two-stage adaptive optimization: a geometric perspective

• 成果类型: Article
• 署名作者: Bertsimas, Dimitris; Bidkhori, Hoda
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0818-5
• 发表日期: 2015
• 页码: 577-594
• 关键词: Robust Optimization; DISCRETE-TIME; DESIGN; POWER

摘要

We consider two-stage adjustable robust linear optimization problems with uncertain right hand side b belonging to a convex and compact uncertainty set u. We provide an a priori approximation bound on the ratio of the optimal affine (in b) solution to the optimal adjustable solution that depends on two fundamental geometric properties of u: (a) the symmetry and (b) the simplex dilation factor of the uncertainty set u and provides deeper insight on the power of affine policies for this class of problems. The bound improves upon a priori bounds obtained for robust and affine policies proposed in the literature. We also find that the proposed a priori bound is quite close to a posteriori bounds computed in specific instances of an inventory control problem, illustrating that the proposed bound is informative.