Stochastic Programming

Data-Driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations

  • Daniel Kuhn
  • Peyman Mohajerin Esfahani
    • Categories Robust Optimization, Stochastic Programming Tags ,

    We consider stochastic programs where the distribution of the uncertain parameters is only observable through a finite training dataset. Using the Wasserstein metric, we construct a ball in the space of (multivariate and non-discrete) probability distributions centered at the uniform distribution on the training samples, and we seek decisions that perform best in view of … Read more

    Distributionally robust expectation inequalities for structured distributions

  • Paul J. Goulart
  • Bart Paul Gerard Van Parys
  • Manfred Morari
    • Categories Convex Optimization, Semi-definite Programming, Stochastic Programming Tags , , ,

    Quantifying the risk of unfortunate events occurring, despite limited distributional information, is a basic problem underlying many practical questions. Indeed, quantifying constraint violation probabilities in distributionally robust programming or judging the risk of financial positions can both be seen to involve risk quantification, notwithstanding distributional ambiguity. In this work we discuss worst-case probability and conditional … Read more

    Decomposition algorithm for large-scale two-stage unit-commitment

  • Jérôme Malick
  • Wim van Ackooij
    • Categories Applications - OR and Management Sciences, Nonsmooth Optimization, Stochastic Programming Tags , , , , ,

    Everyday, electricity generation companies submit a generation schedule to the grid operator for the coming day; computing an optimal schedule is called the unit-commitment problem. Generation companies can also occasionally submit changes to the schedule, that can be seen as intra-daily incomplete recourse actions. In this paper, we propose a two-stage formulation of unit-commitment, wherein … Read more

    Stochastic Optimization using a Trust-Region Method and Random Models

  • Ruobing Chen
  • Matt Menickelly
  • Katya Scheinberg
    • Categories Stochastic Programming, Unconstrained Optimization Tags , , ,

    In this paper, we propose and analyze a trust-region model-based algorithm for solving unconstrained stochastic optimization problems. Our framework utilizes random models of an objective function $f(x)$, obtained from stochastic observations of the function or its gradient. Our method also utilizes estimates of function values to gauge progress that is being made. The convergence analysis … Read more

    A Comment on “Computational Complexity of Stochastic Programming Problems”

  • Grani A. Hanasusanto
  • Daniel Kuhn
  • Wolfram Wiesemann
    • Categories Stochastic Programming

    Although stochastic programming problems were always believed to be computationally challenging, this perception has only recently received a theoretical justification by the seminal work of Dyer and Stougie (Mathematical Programming A, 106(3):423–432, 2006). Amongst others, that paper argues that linear two-stage stochastic programs with fixed recourse are #P-hard even if the random problem data is … Read more

    Extension and Implementation of Homogeneous Self-dual Methods for Symmetric Cones under Uncertainty

  • Baha Alzalg
  • Francesca Maggioni
  • Sebastiano Vitali
    • Categories Linear, Cone and Semidefinite Programming, Stochastic Programming

    Homogeneous self-dual algorithms for stochastic semidefinite programs with finite event space has been proposed by Jin et al. in [12]. Alzalg [8], has adopted their work to derive homogeneous self-dual algorithms for stochastic second-order programs with finite event space. In this paper, we generalize these two results to derive homogeneous self-dual algorithms for stochastic programs … Read more

    Stochastic versus Robust Optimization for a Transportation Problem

  • Marida Bertocchi
  • Francesca Maggioni
  • Florian A. Potra
    • Categories Robust Optimization, Stochastic Programming, Transportation Tags , ,

    In this paper we consider a transportation problem under uncertainty related to gypsum replenishment for a cement producer. The problem is to determine the number of vehicles to book at the beginning of each week to replenish gypsum at all the cement factories of the producer in order to minimize the total cost, given by … Read more

    Asymptotic optimality of Tailored Base-Surge policies in dual-sourcing inventory systems

  • David A. Goldberg
  • Linwei Xin
    • Categories Dynamic Programming, Stochastic Programming, Supply Chain Management Tags , , , , ,

    Dual-sourcing inventory systems, in which one supplier is faster (i.e. express) and more costly, while the other is slower (i.e. regular) and cheaper, arise naturally in many real-world supply chains. These systems are notoriously difficult to optimize due to the complex structure of the optimal solution and the curse of dimensionality, having resisted solution for … Read more

    Risk aversion in multistage stochastic programming: a modeling and algorithmic perspective

  • Tito Homem-de-Mello
  • Bernardo K. Pagnoncelli
    • Categories Stochastic Programming

    We discuss the incorporation of risk measures into multistage stochastic programs. While much attention has been recently devoted in the literature to this type of model, it appears that there is no consensus on the best way to accomplish that goal. In this paper, we discuss pros and cons of some of the existing approaches. … Read more

    Monotonic bounds in multistage mixed-integer linear stochastic programming: theoretical and numerical results

  • Elisabetta Allevi
  • Marida Bertocchi
  • Francesca Maggioni
    • Categories Stochastic Programming

    Multistage stochastic programs bring computational complexity which may increase exponentially in real case problems. For this reason approximation techniques which replace the problem by a simpler one and provide lower and upper bounds to the optimal solution are very useful. In this paper we provide monotonic lower and upper bounds for the optimal objective value … Read more