stochastic programming

A Counterexample to “Threshold Boolean form for joint probabilistic constraints with random technology matrix”

  • James R. Luedtke
    • Categories Stochastic Programming Tags , ,

    Recently, in the paper “Threshold Boolean form for joint probabilistic constraints with random technology matrix” (Math. Program. 147:391–427, 2014), Kogan and Lejeune proposed a set of mixed-integer programming formulations for probabilistically constrained stochastic programs having random constraint matrix and finite support distribution. We show that the proposed formulations do not in general correctly model such … Read more

    A note on sample complexity of multistage stochastic programs

  • Marcus de Mendes C. R. Reaiche
    • Categories Stochastic Programming Tags , , ,

    We derive a \emph{lower bound} for the \emph{sample complexity} of the Sample Average Approximation method for a certain class of multistage stochastic optimization problems. In previous works, \emph{upper bounds} for such problems were derived. We show that the dependence of the \emph{lower bound} with respect to the complexity parameters and the problem’s data are comparable … Read more

    A NEW PARTIAL SAMPLE AVERAGE APPROXIMATION METHOD FOR CHANCE CONSTRAINED PROBLEM

  • Jianqiang Cheng
  • Abdel Lisser
  • Céline Gicquel
    • Categories Stochastic Programming Tags , ,

    In this paper, we present a new scheme of a sampling method to solve chance constrained programs. First of all, a modified sample average approximation, namely Partial Sample Average Approximation (PSAA) is presented. The main advantage of our approach is that the PSAA problem has only continuous variables whilst the standard sample average approximation (SAA) … Read more

    Scenario-Tree Decomposition: Bounds for Multistage Stochastic Mixed-Integer Programs

  • Oleg A. Prokopyev
  • Andrew J. Schaefer
  • Gabriel L. Zenarosa
    • Categories Integer Programming, Parallel Algorithms, Stochastic Programming Tags , ,

    Multistage stochastic mixed-integer programming is a powerful modeling paradigm appropriate for many problems involving a sequence of discrete decisions under uncertainty; however, they are difficult to solve without exploiting special structures. We present scenario-tree decomposition to establish bounds for unstructured multistage stochastic mixed-integer programs. Our method decomposes the scenario tree into a number of smaller … Read more

    Multilevel Optimization Modeling for Risk-Averse Stochastic Programming

  • Jonathan Eckstein
  • Jingnan Fan
  • Deniz Eskandani
    • Categories Stochastic Programming Tags , , ,

    Coherent risk measures have become a popular tool for incorporating risk aversion into stochastic optimization models. For dynamic models in which uncertainty is resolved at more than one stage, however, using coherent risk measures within a standard single-level optimization framework becomes problematic. To avoid severe time-consistency difficulties, the current state of the art is to … Read more

    A scalable bounding method for multi-stage stochastic integer programs

  • Osman Y. Ozaltin
  • Burhaneddin Sandikçi
    • Categories Integer Programming, Parallel Algorithms, Stochastic Programming Tags , , , ,

    Many dynamic decision problems involving uncertainty can be appropriately modeled as multi-stage stochastic programs. However, most practical instances are so large and/or complex that it is impossible to solve them on a single computer, especially due to memory limitations. Extending the work of Sandikci et al. (2013) on two-stage stochastic mixed-integer-programs (SMIPs), this paper develops … Read more

    Fast Approximations for Online Scheduling of Outpatient Procedure Centers

  • Bjorn Berg
  • Brian T. Denton
    • Categories Scheduling Tags , , ,

    This paper presents a new model for online decision making. Motivated by the health care delivery application of dynamically allocating patients to procedure rooms in outpatient procedure centers, the online stochastic extensible bin packing problem is described. The objective is to minimize the combined costs of opening procedure rooms and utilizing overtime to complete a … Read more

    Improving the integer L-shaped method

  • Shabbir Ahmed
  • Gustavo Angulo
  • Santanu S. Dey
    • Categories Integer Programming, Stochastic Programming Tags , , ,

    We consider the integer L-shaped method for two-stage stochastic integer programs. To improve the performance of the algorithm, we present and combine two strategies. First, to avoid time-consuming exact evaluations of the second-stage cost function, we propose a simple modification that alternates between linear and mixed-integer subproblems. Then, to better approximate the shape of the … Read more

    Applying oracles of on-demand accuracy in two-stage stochastic programming – a computational study

  • Csaba I. Fábián
  • Achim Koberstein
  • Leena Suhl
  • Christian Wolf
    • Categories Optimization Software Benchmark, Stochastic Programming Tags , , ,

    Traditionally, two variants of the L-shaped method based on Benders’ decomposition principle are used to solve two-stage stochastic programming problems: the single-cut and the multi-cut version. The concept of an oracle with on-demand accuracy was originally proposed in the context of bundle methods for unconstrained convex optimzation to provide approximate function data and subgradients. In … Read more

    Benders, Nested Benders and Stochastic Programming: An Intuitive Introduction

  • James Murphy
    • Categories Stochastic Programming Tags , , , , , , ,

    This article aims to explain the Nested Benders algorithm for the solution of large-scale stochastic programming problems in a way that is intelligible to someone coming to it for the first time. In doing so it gives an explanation of Benders decomposition and of its application to two-stage stochastic programming problems (also known in this … Read more