On the adaptivity gap in two-stage robust linear optimization under uncertain packing constraints

• 成果类型: Article
• 署名作者: Awasthi, Pranjal; Goyal, Vineet; Lu, Brian Y.
• 署名单位: Rutgers University System; Rutgers University New Brunswick; Columbia University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1222-8
• 发表日期: 2019
• 页码: 313-352
• 关键词: POWER

摘要

In this paper, we study the performance of static solutions in two-stage adjustable robust packing linear optimization problem with uncertain constraint coefficients. Such problems arise in many important applications such as revenue management and resource allocation problems where demand requests have uncertain resource requirements. The goal is to find a two-stage solution that maximizes the worst case objective value over all possible realizations of the second-stage constraints from a given uncertainty set. We consider the case where the uncertainty set is column-wise and constraint-wise (any constraint describing the set involve entries of only a single column or a single row). This is a fairly general class of uncertainty sets to model constraint coefficient uncertainty. We show that the two-stage adjustable robust problem is (logn)-hard to approximate. On the positive side, we show that a static solution is an O(lognmin(log,log(m+n)))-approximation for the two-stage adjustable robust problem where m and n denote the numbers of rows and columns of the constraint matrix and is the maximum possible ratio of upper bounds of the uncertain constraint coefficients. Therefore, for constant , surprisingly the performance bound for static solutions and therefore, the adaptivity gap matches the hardness of approximation for the adjustable problems. Furthermore, in general the static solution provides nearly the best efficient approximation for the two-stage adjustable robust problem.