15th EUROPT Workshop on Advances in Continuous Optimization
Montréal, Canada, 12 — 14 juillet 2017
15th EUROPT Workshop on Advances in Continuous Optimization
Montréal, Canada, 12 — 14 juillet 2017
Multistage Robust Optimization
14 juil. 2017 10h30 – 11h45
Salle: PWC
Présidée par Erick Delage
3 présentations

10h30  10h55
Distributed Adjustable Robust Optimization
Conventional robust optimization (RO) considers that uncertain parameters belong to some compact (uncertainty) set and all variables must be determined before the realization of uncertain parameters becomes known. All variables represent "here and now" decisions. Often a subset of variables referred to as adjustable can be chosen after the realization of the uncertain data while others (nonadjustable) must be determined before its realization. The former variables represent "wait and see" decisions that can be made when revealing part of the uncertain data and that can adjust to the corresponding part of the data. In this case, the socalled adjustable RO (ARO) method produces adjustable robust counterparts (ARC) that are less conservative than their corresponding RC though computationally harder. In the nonrobust context, decomposition methods provide a useful method where the structure of the original problem (OP) can be exploited in order to split it into subproblems that are repeatedly solved in order to obtain further information about its structure that can be incorporated into a master problem (MP). The major strength of these methods stems from their ability to reformulate the OP into a MP together with the generation of subproblems that are significantly easier to solve than the OP and that can be solved concurrently (if subproblems are independent). However, the decomposable structure of the uncertain OP may disappear when formulating its (A)RC using standard techniques. Hence, preserving the decomposability property becomes essential in order to allow distributed solving of (A)RCs. We analyze decomposability preserving robust formulations of uncertain mixedinteger programs and provide a preliminary characterization of the fundamental tradeoff between decomposability and robustification.

10h55  11h20
On the Optimality of Affine Policies for Budget of Uncertainty Sets
We consider a twostage adjustable robust optimization problem with linear covering constraints and uncertain right hand side belonging to a budget of uncertainty set. This problem is hard to approximate with a factor $\Omega(\log n)$ where $n$ is the number of secondstage decision variables. We show that surprisingly affine policies provide nearly the best possible approximation for budget of uncertainty sets. We also discuss generalizations to the case when the uncertainty set is given by multiple knapsack constraints. This is joint work with Omar El Housni

11h20  11h45
Robust Dual Dynamic Programming
We propose a robust dual dynamic programming (RDDP) scheme for multistage robust optimization problems. The RDDP scheme takes advantage of the decomposable nature of these problems by bounding the costs arising in the future stages through inner and outer approximations. In contrast to Stochastic Dual Dynamic Programming, we refine the approximations using as a devise our inner approximations to determine the points of refinement. We prove that RDDP converges deterministically in finite time. We demonstrate the promising performance of our algorithm in stylized instances of inventory management problems.