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

Author： dempster M.A.H. Thompson R.T.

Publisher： Springer Publishing Company

ISSN： 0254-5330

Source： Annals of Operations Research, Vol.90, Iss.1, 1999-01, pp. : 161-184

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

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.