Solving multistage stochastic network programs on massively parallel computers |
| |
Authors: | Soren S Nielsen Stavros A Zenios |
| |
Institution: | (1) Management Science and Information Systems, University of Texas at Austin, 78712 Austin, TX, USA;(2) University of Cyprus, Nicosia, Cyprus |
| |
Abstract: | Multi-stage stochastic programs are typically extremely large, and can be prohibitively expensive to solve on the computer.
In this paper we 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. We 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.
Research partially supported by NSF grants CCR-9104042 and SES-91-00216, and AFOSR grant 91-0168. Computing resources were
made available by AHPCRC at the University of Minnesota, and by NPAC at Syracuse University, New York. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|