Piecewise static policies for two-stage adjustable robust linear optimization

• 成果类型: Article
• 署名作者: El Housni, Omar; Goyal, Vineet
• 署名单位: Columbia University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1142-7
• 发表日期: 2018
• 页码: 649-665
• 关键词: convex-optimization; finite adaptability; affine policies; uncertainty; PROGRAMS

摘要

In this paper, we consider two-stage adjustable robust linear optimization problems under uncertain constraints and study the performance of piecewise static policies. These are a generalization of static policies where we divide the uncertainty set into several pieces and specify a static solution for each piece. We show that in the worst-case, there is no piecewise static policy with a polynomial number of pieces that has a significantly better performance than an optimal static policy. This is quite surprising as piecewise static policies are significantly more general than static policies. The proof is based on a combinatorial argument and the structure of piecewise static policies.