3 présentations

• 
  10h30 - 10h55

  Distributed Adjustable Robust Optimization

  • Dimitri Papadimitriou, prés., Bell Labs

  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

  • Vineet Goyal, prés., Columbia University
  • Omar El Housni, Columbia University

  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

  • Angelos Georghiou, prés., McGill University
  • Angelos Tsoukalas, American University of Beirut
  • Wolfram Wiesemann, Imperial College Business School

  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.