A Massively Parallel Algorithm for Nonlinear Stochastic Network Problems

Soren S. Nielsen and Stavros Zenios
Additional contact information
Soren S. Nielsen: The University of Texas, Austin, Texas

Operations Research, 1993, vol. 41, issue 2, 319-337

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 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—8,192 scenarios with a deterministic equivalent nonlinear program with 868,367 constraints and 2,474,017 variables—are solved within a few minutes. We report extensive numerical results regarding the effects of stochasticity on the efficiency of the algorithm.

Keywords: computers/computer science: massively parallel; networks/graphs: stochastic generalized networks; programming: stochastic; nonlinear algorithms (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.41.2.319 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:41:y:1993:i:2:p:319-337

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().