Decomposition Algorithms for Stochastic Programming on a Computational Grid
Preprint
Abstract
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 type (with the workers being used to solve second-stage problems, and the MW runtime support library (which supports master-worker computations) is key to the implementation. Computational results are presented on large sample average approximations of problems from the literature.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- A Comprehensive Input Format for Stochastic Linear ProgramsAnnals of Operations Research, 2001
- Building and Solving Large-Scale Stochastic Programs on an Affordable Distributed Computing SystemAnnals of Operations Research, 2000
- A parallel implementation of the nested decomposition algorithm for multistage stochastic linear programsMathematical Programming, 1996
- A cutting plane method from analytic centers for stochastic programmingMathematical Programming, 1995
- Network planning with random demandTelecommunication Systems, 1994
- Weak Sharp Minima in Mathematical ProgrammingSIAM Journal on Control and Optimization, 1993
- Parallel decomposition of multistage stochastic programming problemsMathematical Programming, 1993
- Proximity control in bundle methods for convex nondifferentiable minimizationMathematical Programming, 1990
- A regularized decomposition method for minimizing a sum of polyhedral functionsMathematical Programming, 1986
- Partitioning procedures for solving mixed-variables programming problemsNumerische Mathematik, 1962