Parallel decomposition of multistage stochastic programming problems

Research output: Contribution to journalArticlepeer-review

109 Scopus citations


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
Issue number1-3
StatePublished - Jan 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


  • Stochastic programming
  • decomposition
  • dynamic programming
  • parallel computing


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

Cite this