4 Presentations

• 
  10:30 AM - 10:55 AM

  Piecewise static policies for two-stage adjustable robust linear optimization

  • Vineet Goyal, Columbia University
  • Omar El Housni, presenter, Columbia University

  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 general 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.

• 
  10:55 AM - 11:20 AM

  Piecewise affine policies for two-stage robust optimization under demand uncertainty

  • Aharon Ben-Tal, Technion
  • Omar El Housni, Columbia University
  • Vineet Goyal, presenter, Columbia University
  • Brian Lu, Columbia University

  We consider the problem of designing good piecewise affine policies for two-stage adjustable robust linear optimization problems under right hand side uncertainty. Such problems arise in many applications where we need to satisfy an uncertain demand with minimum possible cost. It is well known that a piecewise affine policy is optimal although the number of pieces can be exponentially many. One of the significant challenges in designing a piecewise affine policy arises from constructing good pieces of the uncertainty set. We introduce a new framework for constructing piecewise affine policies where we "approximate" the uncertainty set by a simplex and construct a piecewise affine policy based on the map from the uncertainty set to the simplex. Our piecewise affine policy has exponentially many pieces but can be computed efficiently and in many cases, even more efficiently than computing the optimal affine policy. Furthermore, the performance of our piecewise affine policy is significantly better than the affine policy.

• 
  11:20 AM - 11:45 AM

  Linearized robust counterparts of two-stage robust optimization problem

  • Amir Ardestani-Jaafari, presenter, University of British Columbia
  • Erick Delage, GERAD, HEC Montréal

  We study two-stage robust optimization problem wherein some decisions can be made when the actual data is revealed. Since this problem is computationally intractable we propose a conservative tractable approximation scheme for this problem based on linearizing the cross terms that appears due to the recourse problem. We relate this new scheme to methods that are based on exploiting affine decision rules. Furthermore, we show that our proposed method can be exploited to provide exact solutions in a family of robust multi-item newsvendor problem. Using a robust facility location problem, we also show how our proposed method can be used to derive conservative approximations that are tighter than existing tractable methods.

• 
  11:45 AM - 12:10 PM

  Designing inventory network with adjustable robust optimization

  • Peter Zhang, presenter, MIT
  • David Simchi-Levi, MIT
  • Nikolaos Trichakis, Harvard

  We study a network flow problem with uncertain demand that involves two sets of decisions: (1) inventory placement on the nodes prior to demand realization, and (2) allocation of the inventory to satisfy demand. We show that affine policy is optimal under a tree structure and budgeted uncertainty set. This particular setup is motivated by the problem of designing Strategic National Stockpile, a federal response network for public health emergencies in the United States.