Parallel decomposition of multistage stochastic programming problems

Research output: Contribution to journalArticlepeer-review

108 Scopus citations

Abstract

A new decomposition method for multistage stochastic linear programming problems is proposed. A multistage stochastic problem is represented in a tree-like form and with each node of the decision tree a certain linear or quadratic subproblem is associated. The subproblems generate proposals for their successors and some backward information for their predecessors. The subproblems can be solved in parallel and exchange information in an asynchronous way through special buffers. After a finite time the method either finds an optimal solution to the problem or discovers its inconsistency. An analytical illustrative example shows that parallelization can speed up computation over every sequential method. Computational experiments indicate that for large problems we can obtain substantial gains in efficiency with moderate numbers of processors.

Original languageEnglish (US)
Pages (from-to)201-228
Number of pages28
JournalMathematical Programming
Volume58
Issue number1-3
DOIs
StatePublished - Jan 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Stochastic programming
  • decomposition
  • dynamic programming
  • parallel computing

Fingerprint

Dive into the research topics of 'Parallel decomposition of multistage stochastic programming problems'. Together they form a unique fingerprint.

Cite this