Massively Parallel Proximal Algorithms for Solving Linear Stochastic Network Programs
Soren S. Nielsen, Stavros A. Zenios · The International Journal of High Performance Computing Applications · 1993
We develop an algorithm for solving two-stage sto chastic linear programs with network recourse. The algorithm is based on the proximal minimization algo rithm with D-functions and uses a primal-dual row- action algorithm to solve the resulting, strictly convex subproblems. The stochastic program is reformulated into a form that decomposes by scenario, thus making the algorithm suitable for parallel implementation. In addition, the constraints of each scenario subproblem (which are network problems) can be iterated upon concurrently, allowing for a massively parallel imple mentation. The algorithm is implemented on a Con nection Machine 2 with up to 32k processors. It is shown to be very effective in solving problems with up to 2,048 scenarios, where the deterministic equivalent program has 217,103 constraints and 618,529 variables.