Stochastic Programming

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. Citation Preprint, Mathematics and Computer Science Division, Argonne National … Read more