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 so-called adjustable RO (ARO) method produces adjustable robust counterparts (ARC) that are less conservative than their corresponding RC though computationally harder. In the non-robust 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 mixed-integer 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 two-stage 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 second-stage 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 multi-stage 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.