On Massively Parallel Algorithm for Nonlinear Stochastic Network Problems

Abstract

We develop an algorithm for solving nonlinear two-stage stochastic problems with network recourse. The algorithm is based on the framework of row-action methods. The problem is formulated by replicating the first-stage variables and then adding nonanticipativity side constraints. A series of (independent) deterministic network problems are solved at each step of the algorithm, followed by an iterative step over the nonanticipativity constraints. The solution point of the iterates over the non-anticipativity constraints can be obtained analytically. The row-action nature of the algorithm makes it suitable for parallel implementations. A data representation of the problem is developed that permits the massively parallel solution of all the scenario subproblems concurrently. The algorithm is implemented on a Connection Machine CM-2 with up to 32K processing elements and achieves computing rates of 250 MFLOPS. Very large problems - 8192 scenarios with a deterministic equivalent nonlinear program with 1,272,160 variables and 495,616 constraints - are solved within a few minutes. We report extensive numerical results regarding the effects of stochasticity on the efficiency of the algorithm.