A PARALLEL IMPLEMENTATION OF THE NESTED DECOMPOSITION ALGORITHM FOR MULTISTAGE STOCHASTIC LINEAR-PROGRAMS

Multistage stochastic linear programs can represent a variety of pract ical decision problems. Solving a multistage stochastic program can be viewed as solving a large tree of linear programs. A common approach for solving these problems is the nested decomposition algorithm, whic h moves up and down the tree by solving nodes and passing information among nodes. The natural independence of subtrees suggests that much o f the computational effort of the nested decomposition algorithm can r un in parallel across small numbers of fast processors. This paper exp lores the advantages of such parallel implementations over serial impl ementations and compares alternative sequencing protocols for parallel processors. Computational experience on a large test set of practical problems with up to 1.5 million constraints and almost 5 million vari ables suggests that parallel implementations may indeed work well, but they require careful attention to processor load balancing.