Wednesday August 31

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 finance. 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 specifies constraints that must be satisfied 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 finite 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 finite 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 first 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- ficiently, 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 finitely convergent algorithm for two-stage stochastic programs with a finite 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