  


On the Adaptivity Gap in Twostage Robust Linear Optimization under Uncertain Constraints
Pranjal Awasthi (pawashtics.princeton.edu) Abstract: In this paper, we study the performance of static solutions in twostage 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 twostage 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 columnwise and constraintwise (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 twostage adjustable robust problem is \Omega(\log n)hard to approximate. On the positive side, we show that a static solution is an O(\log n \min(\log \Gamma, \log(m+n))approximation for the twostage adjustable robust problem where m and n denote the numbers of rows and columns of the constraint matrix and \Gamma is the maximum possible ratio of upper bounds of the uncertain constraint coefficients. Therefore, for constant \Gamma, surprisingly the performance bound for static solutions matches the hardness of approximation for the adjustable problem. Furthermore, in general the static solution provides nearly the best efficient approximation for the twostage adjustable robust problem. Keywords: Robust Optimization; Approximation Algorithms; Hardness of Approximation Category 1: Robust Optimization Category 2: Combinatorial Optimization (Approximation Algorithms ) Citation: Download: [PDF] Entry Submitted: 12/22/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  