A massively parallel algorithm for nonlinear stochastic network problems

A massively parallel algorithm for nonlinear stochastic network problems

0.00 Avg rating0 Votes
Article ID: iaor1994228
Country: United States
Volume: 41
Issue: 2
Start Page Number: 319
End Page Number: 337
Publication Date: Mar 1993
Journal: Operations Research
Authors: ,
Keywords: networks, stochastic processes, programming: nonlinear
Abstract:

The paper develops 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 nonanticipativity constraints is 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 276 MFLOPS. Very large problems-8192 scenarios with a deterministic equivalent nonlinear program with 868367 constraints and 2474017 variables-are solved within a few minutes. The authors report extensive numerical results regarding the effects of stochasticity on the efficiency of the algorithm.

Reviews

Required fields are marked *. Your email address will not be published.