Stochastic Programming

Tutorial on risk neutral, distributionally robust and risk averse multistage stochastic programming

  • Alexander Shapiro
    • Categories Robust Optimization, Stochastic Programming Tags , , , , , ,

    In this tutorial we discuss several aspects of modeling and solving multistage stochastic programming problems. In particular we discuss distributionally robust and risk averse approaches to multistage stochastic programming, and the involved concept of time consistency. This tutorial is aimed at presenting a certain point of view of multistage stochastic programming, and can be viewed … Read more

    Stochastic dual dynamic programming with stagewise dependent objective uncertainty

  • Regan Baucke
  • Anthony Downward
  • Oscar Dowson
    • Categories Stochastic Programming Tags , , , ,

    We present a new algorithm for solving linear multistage stochastic programming problems with objective function coefficients modeled as a stochastic process. This algorithm overcomes the difficulties of existing methods which require discretization. Using an argument based on the finiteness of the set of possible cuts, we prove that the algorithm converges almost surely. Finally, we … Read more

    A deterministic algorithm for solving stochastic minimax dynamic programmes

  • Regan Baucke
  • Anthony Downward
  • Golbon Zakeri
    • Categories Dynamic Programming, Robust Optimization, Stochastic Programming Tags , , , , , , , , ,

    In this paper, we present an algorithm for solving stochastic minimax dynamic programmes where state and action sets are convex and compact. A feature of the formulations studied is the simultaneous non-rectangularity of both `min’ and `max’ feasibility sets. We begin by presenting convex programming upper and lower bound representations of saddle functions — extending … Read more

    Inexact cuts in Deterministic and Stochastic Dual Dynamic Programming applied to linear optimization problems

  • Vincent Guigues
    • Categories Stochastic Programming

    We introduce an extension of Dual Dynamic Programming (DDP) to solve linear dynamic programming equations. We call this extension IDDP-LP which applies to situations where some or all primal and dual subproblems to be solved along the iterations of the method are solved with a bounded error (inexactly). We provide convergence theorems both in the … Read more

    Convergence Analysis of Sample Average Approximation of Two-stage Stochastic Generalized Equations

  • Xiaojun Chen
  • Alexander Shapiro
  • Hailin Sun
    • Categories Stochastic Programming Tags , , , ,

    A solution of two-stage stochastic generalized equations is a pair: a first stage solution which is independent of realization of the random data and a second stage solution which is a function of random variables. This paper studies convergence of the sample average approximation of two-stage stochastic nonlinear generalized equations. In particular an exponential rate … Read more

    Large neighbourhood Benders’ search

  • Stephen J. Maher
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , ,

    A general enhancement of the Benders’ decomposition algorithm can be achieved through the improved use of large neighbourhood search heuristics within mixed-integer programming solvers. While mixed-integer programming solvers are endowed with an array of large neighbourhood search heuristics, their use is typically limited to finding solutions to the Benders’ decomposition master problem, which may be … Read more

    Bicriteria Approximation of Chance Constrained Covering Problems

  • Shabbir Ahmed
  • Weijun Xie
    • Categories Combinatorial Optimization, Robust Optimization, Stochastic Programming

    A chance constrained optimization problem involves constraints with random data which can be violated with probability bounded above by a prespecified small risk parameter. Such constraints are used to model reliability requirements in a variety of application areas such as finance, energy, service and manufacturing. Except under very special conditions, chance constrained problems are extremely … Read more

    Solving joint chance constrained problems using regularization and Benders’ decomposition

  • Lukáš Adam
  • Holger Heitsch
  • René Henrion
  • Martin Branda
    • Categories Stochastic Programming

    We consider stochastic programs with joint chance constraints with discrete random distribution. We reformulate the problem by adding auxiliary variables. Since the resulting problem has a non-regular feasible set, we regularize it by increasing the feasible set. We solve the regularized problem by iteratively solving a master problem while adding Benders’ cuts in a slave … Read more

    Wasserstein Distributionally Robust Optimization and Variation Regularization

  • Xi Chen
  • Rui Gao
  • Anton J. Kleywegt
    • Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming

    Wasserstein distributionally robust optimization (DRO) has recently achieved empirical success for various applications in operations research and machine learning, owing partly to its regularization effect. Although the connection between Wasserstein DRO and regularization has been established in several settings, existing results often require restrictive assumptions, such as smoothness or convexity, that are not satisfied by … Read more

    A Stochastic Trust Region Algorithm Based on Careful Step Normalization

  • Frank E. Curtis
  • Katya Scheinberg
  • Rui Shi
    • Categories Nonlinear Optimization, Stochastic Programming, Unconstrained Optimization Tags , , , , , ,

    An algorithm is proposed for solving stochastic and finite sum minimization problems. Based on a trust region methodology, the algorithm employs normalized steps, at least as long as the norms of the stochastic gradient estimates are within a specified interval. The complete algorithm—which dynamically chooses whether or not to employ normalized steps—is proved to have … Read more