## Wednesday, August 31, Stochastic Optimization

**Workshop Chair: Anton Kleywegt**

**Time:** 08:30 – 09:30

**Speaker:** Alexander Shapiro

**Title:** Stochastic Programming tutorial

**Abstract:** Optimization problems involving stochastic models occur in almost all areas of science and engineering, such as telecommunications, medicine, and ﬁnance. This tutorial focuses on optimization problems involving uncertain parameters and discusses theoretical foundations and recent advances in the area of stochastic programming.

**Time:** 09:45 – 10:45

**Speaker:** Anton Kleywegt

**Title:** Distributionally Robust Stochastic Optimization tutorial

**Abstract:** There are various approaches to optimization under uncertainty. The robust optimization approach speciﬁes constraints that must be satisﬁed for all values of the uncertain variables in a chosen uncertainty set. This is a reasonable approach for many applications, but in other applications it has several shortcomings, such as being overly conservative (it hedges against the worst possible outcome of the uncertain variables in the chosen uncertainty set), being very sensitive to the somewhat arbitrary choice of uncertainty set, and not taking into account available data that have some relevance for which future values of the uncertain variables to hedge against. The stochastic optimization approach models uncertain variables as random variables with known probability distributions. In practice the true probability distribution may not be known, and in some problems there will not be multiple replications of the same random variable (for example, for each presidential election in the USA there will be only one future realization) so that the notion of a true probability distribution does not even apply. Distributionally robust stochastic optimization is an approach to optimization under uncertainty in which one hedges against a set of probability distributions, possibly taking into account available data. This seems to be a reasonable approach to optimization under uncertainty for many applications. The tutorial will discuss various types of distributionally robust stochastic optimization.

**Time:** 11:00 – 12:00

**Speaker:** Shabbir Ahmed

**Title:** Stochastic integer programming tutorial or Chance constrained stochastic pro- gramming tutorial

**Time:** 12:00 – 13:30 – **Lunch**

**Time:** 13:30 – 14:00

**Speaker:** Francesca Maggioni

**Title:** Worst-case analysis of Rolling Horizon Approach in Multistage Stochastic Pro- gramming: a Transportation Procurement Problem

**Time:** 14:00 – 14:30

**Speaker:** Enlu Zhou

**Title:** Computing Dual Bounds in Dynamic Programming

**Abstract:** I will talk about the information relaxation approach and the associated duality theory in dynamic programming. Based on the theory, we have developed a few computational approaches to computing dual bounds on the value function for a given sub-optimal policy. In particular I will focus on two recent works: 1) a practical information relaxation approach for weakly coupled dynamic programs; 2) an efficient regression approach for general dynamic programs.

**Time:** 14:45 – 15:15

**Speaker:** Jikai Zou

**Title:** Nested Decomposition of Multistage Stochastic Integer Programs with Binary State Variables

**Abstract:** We propose a valid nested decomposition algorithm for multistage stochastic integer programming problems when the state variables are binary. We prove ﬁnite convergence of the algorithm as long as the cuts satisfy some sufficient conditions. We discuss the use of well known Benders and integer optimality cuts within this algorithm, and introduce new cuts derived from a Lagrangian relaxation corresponding to a reformulation of the problem where local copies of state variables are introduced. We propose a stochastic variant of this algorithm and prove its ﬁnite convergence with probability one. Numerical experiment on a large-scale generation expansion planning problem will be presented.

**Time:** 15:15 – 15:45

**Speaker:** Weijun Xie

**Title:** Nonanticipative duality, relaxations, and formulations for chance-constrained stochastic programs

**Abstract:** We propose two new Lagrangian dual problems for chance-con-strained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer program- ming (MIP) formulation. For a given dual solution, the associated Lagrangian relax- ation bounds can be calculated by solving a set of single scenario subproblems and then solving a single knapsack problem. We also derive two new primal MIP formu- lations and demonstrate that for chance-constrained linear programs, the continuous relaxations of these formulations yield bounds equal to the proposed dual bounds. We propose a new heuristic method and two new exact algorithms based on these duals and formulations. The ﬁrst exact algorithm applies to chance-constrained binary pro- grams, and uses either of the proposed dual bounds in concert with cuts that eliminate solutions found by the subproblems. The second exact method is a branch-and-cut algorithm for solving either of the primal formulations. Our computational results indicate that the proposed dual bounds and heuristic solutions can be obtained ef- ﬁciently, and the gaps between the best dual bounds and the heuristic solutions are small. This is joint work with Shabbir Ahmed, James Luedtke and Yongjia Song.

**Time:** 16:00 – 16:30

**Speaker:** Kevin Ryan

**Title:** Optimization Driven Scenario Grouping

**Abstract:** Scenario decomposition algorithms for stochastic programs compute bounds by dualizing all nonanticipativity constraints and solving individual scenario problems. We develop an optimization problem that selects a set of nonanticipativity constraints to re-enforce, placing scenarios into ‘groups’. We show that the proposed grouping problem is NP-hard in general, identify a polynomially solvable case, and present a mixed integer programming formulation. Its effectiveness is demonstrated on a set of standard test instances for two-stage 0-1 stochastic programs. The idea is extended to propose a ﬁnitely convergent algorithm for two-stage stochastic programs with a ﬁnite feasible region.

**Time:** 16:30 – 17:00

**Speaker:** Francesca Maggioni

**Title:** Bounds and Approximations in Multistage Stochastic Programs

**Time:** 17:00 – 17:30

**Speaker:** Rui Gao

**Title:** Stochastic Optimization for Distributed System Design