EVPI‐based importance sampling solution proceduresfor multistage stochastic linear programmeson parallel MIMD architectures

M.A.H. Dempster and R.T. Thompson

Annals of Operations Research, 1999, vol. 90, issue 0, 184 pages

Abstract: Multistage stochastic linear programming has many practical applications for problemswhose current decisions have to be made under future uncertainty. There are a variety ofmethods for solving the deterministic equivalent forms of these dynamic problems, includingthe simplex and interior‐point methods and nested Benders decomposition, which decomposesthe original problem into a set of smaller linear programming problems and hasrecently been shown to be superior to the alternatives for large problems. The Benderssubproblems can be visualised as being attached to the nodes of a tree which is formed fromthe realisations of the random data process determining the uncertainty in the problem. Thispaper describes a parallel implementation of the nested Benders algorithm which employsa farming technique to parallelize nodal subproblem solutions. Differing structures of thetest problems cause differing levels of speed‐up on a variety of multicomputing platforms:problems with few variables and constraints per node do not gain from this parallelisation.We therefore employ stage aggregation to such problems to improve their parallel solutionefficiency by increasing the size of the nodes and therefore the time spent calculating relativeto the time spent communicating between processors. A parallel version of a sequentialimportance sampling solution algorithm based on local expected value of perfect information(EVPI) is developed which is applicable to extremely large multistage stochastic linearprogrammes which either have too many data paths to solve directly or a continuous distributionof possible realisations. It utilises the parallel nested Benders algorithm and a parallelversion of an algorithm designed to calculate the local EVPI values for the nodes of the treeand achieves near linear speed‐up. Copyright Kluwer Academic Publishers 1999

Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018956530304 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:90:y:1999:i:0:p:161-184:10.1023/a:1018956530304

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018956530304

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().