Optimization Online


Decomposition Algorithms for Stochastic Programming on a Computational Grid

Jeff Linderoth (jtl3***at***lehigh.edu)
Stephen Wright (swright***at***cs.wisc.edu)

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: stochastic programming, parallel algorithms

Category 1: Stochastic Programming

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: Optimization Technical Report 02-07, Computer Sciences Department, University of Wisconsin-Madison

Download: [Postscript][PDF]

Entry Submitted: 04/17/2001
Entry Accepted: 04/17/2001
Entry Last Modified: 09/30/2002

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society