Stochastic Programming

The Sample Average Approximation Method for Stochastic Programs with Integer Recourse

  • Shabbir Ahmed
  • Alexander Shapiro
    • Categories Integer Programming, Stochastic Approaches, Stochastic Programming Tags , , ,

    This paper develops a solution strategy for two-stage stochastic programs with integer recourse. The proposed methodology relies on approximating the underlying stochastic program via sampling, and solving the approximate problem via a specialized optimization algorithm. We show that the proposed scheme will produce an optimal solution to the true problem with probability approaching one exponentially … Read more

    Statistical inference of multistage stochastic programming problems

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

    We discuss in this paper statistical inference of sample average approximations of multistage stochastic programming problems. We show that any random sampling scheme provides a valid statistical lower bound for the optimal value of the true problem. However, in order for such lower bound to be consistent one needs to employ the conditional sampling procedure. … Read more

    The Empirical Behavior of Sampling Methods for Stochastic Programming

  • Jeff Linderoth
  • Alexander Shapiro
  • Stephen Wright
    • Categories Stochastic Programming Tags , ,

    We investigate the quality of solutions obtained from sample-average approximations to two-stage stochastic linear programs with recourse. We use a recently developed software tool executing on a computational grid to solve many large instances of these problems, allowing us to obtain high-quality solutions and to verify optimality and near-optimality of the computed solutions in various … Read more

    The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study

  • Shabbir Ahmed
  • Anton J. Kleywegt
  • George L. Nemhauser
  • Alexander Shapiro
  • Bram Verweij
    • Categories Cutting Plane Approaches, Stochastic Programming, Transportation Tags , , ,

    The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. … Read more

    On a new collection of stochastic linear programming testproblems

  • K. A. Ariyawansa
  • Andrew J. Felt
    • Categories Stochastic Programming Tags

    The purpose of this paper is to introduce a new test problem collection for stochastic linear programming that the authors have recently begun to assemble. While there are existing stochastic programming test problem collections, our new collection has three features that distinguish it from existing collections. First, our collection is web-based with free public access, … Read more

    Decomposition Algorithms for Stochastic Programming on a Computational Grid

  • Jeff Linderoth
  • Stephen Wright
    • Categories Parallel Algorithms, Stochastic Programming Tags ,

    We describe algorithms for two-stage stochastic linear programming with recourse and their implementation on a grid computing platform. In particular, we examine serial and asynchronous versions of the L-shaped method and a trust-region method. The parallel platform of choice is the dynamic, heterogeneous, opportunistic platform provided by the Condor system. The algorithms are of master-worker … Read more

    On Robust Optimization of Two-Stage Systems

  • Shabbir Ahmed
  • Samer Takriti
    • Categories Convex Optimization, Robust Optimization, Stochastic Programming Tags , ,

    Robust optimization extends stochastic programming models by incorporating measures of variability into the objective function. This paper explores robust optimization in the context of two-stage planning systems. First, we propose the use of a generalized Benders decomposition algorithm for solving robust models. Next, we argue that using an arbitrary measure for variability can lead to … Read more

    A Multi-stage Stochastic Integer Programming Approach for Capacity Expansion under Uncertainty

  • Shabbir Ahmed
  • Alan J. King
  • Gyana Parija
    • Categories Integer Programming, Production and Logistics, Stochastic Programming Tags , , , ,

    This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation … Read more

    Optimization on Computational Grids

  • Stephen Wright
    • Categories Branch and Cut Algorithms, Parallel Algorithms, Stochastic Programming Tags , , , ,

    We define the concept of a computational grid, and describe recent work in solving large and complex optimization problems on this type of platform; in particular, integer programming, the quadratic assignment problem, and stochastic programming problems. This article focuses on work conducted in the metaneos project. CitationPreprint, Mathematics and Computer Science Division, Argonne National Laboratory. … Read more