Solving multistage stochastic network programs on massively parallel computers

Multi-stage stochastic programs are typically extremely large, and can be prohibitively expensive to solve on the computer. In this paper the authors develop an algorithm for multistage programs that integrates the primal-dual row-action framework with proximal minimization. The algorithm exploits the structure of stochastic programs with network recourse, using a suitable problem formulation based on split variables, to decompose the solution into a large number of simple operations. It is therefore possible to use massively parallel computers to solve large instances of these problems. The algorithm is implemented on a Connection Machine CM-2 with up to 32K processors. The authors solve stochastic programs from an application from the insurance industry, as well as random problems, with up to 9 stages, and with up to 16392 scenarios, where the deterministic equivalent programs have a half million constraints and 1.3 million variables.