Journées de l'optimisation 2016
HEC Montréal, Québec, Canada, 2 — 4 mai 2016
WA3 TwoStage Robust Optimization II
4 mai 2016 10h30 – 12h10
Salle: EY
Présidée par Erick Delage
4 présentations

10h30  10h55
Piecewise static policies for twostage adjustable robust linear optimization
We consider twostage 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.

10h55  11h20
Piecewise affine policies for twostage robust optimization under demand uncertainty
We consider the problem of designing good piecewise affine policies for twostage 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.

11h20  11h45
Linearized robust counterparts of twostage robust optimization problem
We study twostage 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 multiitem 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.

11h45  12h10
Designing inventory network with adjustable robust optimization
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.