A parallel computation approach for solvingmultistage stochastic network problems

L.F. Escudero, J.L. De La Fuente, C. García and F.J. Prieto

Annals of Operations Research, 1999, vol. 90, issue 0, 160 pages

Abstract: This paper presents a parallel computation approach for the efficient solution of verylarge multistage linear and nonlinear network problems with random parameters. Theseproblems result from particular instances of models for the robust optimization of networkproblems with uncertainty in the values of the right‐hand side and the objective functioncoefficients. The methodology considered here models the uncertainty using scenarios tocharacterize the random parameters. A scenario tree is generated and, through the use offull‐recourse techniques, an implementable solution is obtained for each group of scenariosat each stage along the planning horizon. As a consequence of the size of the resulting problems, and the special structure of theirconstraints, these models are particularly well‐suited for the application of decompositiontechniques, and the solution of the corresponding subproblems in a parallel computationenvironment. An augmented Lagrangian decomposition algorithm has been implementedon a distributed computation environment, and a static load balancing approach has beenchosen for the parallelization scheme, given the subproblem structure of the model. Largeproblems ‐ 9000 scenarios and 14 stages with a deterministic equivalent nonlinear modelhaving 166000 constraints and 230000 variables ‐ are solved in 45 minutes on a cluster offour small (11 Mflops) workstations. An extensive set of computational experiments isreported; the numerical results and running times obtained for our test set, composed oflarge‐scale real‐life problems, confirm the efficiency of this procedure. Copyright Kluwer Academic Publishers 1999

Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018904513466 (text/html)
Access to full text is restricted to subscribers.

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:spr:annopr:v:90:y:1999:i:0:p:131-160:10.1023/a:1018904513466

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018904513466

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().