A parallel computation approach for solving multistage stochastic network problems

e-Archivo Repository

Show simple item record

dc.contributor.author Escudero, L. F.
dc.contributor.author Fuente, J. L. de la
dc.contributor.author García, Cristina
dc.contributor.author Prieto, Francisco J.
dc.date.accessioned 2012-10-08T18:45:03Z
dc.date.available 2012-10-08T18:45:03Z
dc.date.issued 1999
dc.identifier.bibliographicCitation Annals of Operations Research, 1999, v. 90, p. 131-160
dc.identifier.issn 0254-5330
dc.identifier.uri http://hdl.handle.net/10016/15610
dc.description The original publication is available at www.springerlink.com
dc.description.abstract This paper presents a parallel computation approach for the efficient solution of very large multistage linear and nonlinear network problems with random parameters. These problems result from particular instances of models for the robust optimization of network problems with uncertainty in the values of the right-hand side and the objective function coefficients. The methodology considered here models the uncertainty using scenarios to characterize the random parameters. A scenario tree is generated and, through the use of full-recourse techniques, an implementable solution is obtained for each group of scenarios at each stage along the planning horizon. As a consequence of the size of the resulting problems, and the special structure of their constraints, these models are particularly well-suited for the application of decomposition techniques, and the solution of the corresponding subproblems in a parallel computation environment. An augmented Lagrangian decomposition algorithm has been implemented on a distributed computation environment, and a static load balancing approach has been chosen for the parallelization scheme, given the subproblem structure of the model. Large problems – 9000 scenarios and 14 stages with a deterministic equivalent nonlinear model having 166000 constraints and 230000 variables – are solved in 45 minutes on a cluster of four small (11 Mflops) workstations. An extensive set of computational experiments is reported; the numerical results and running times obtained for our test set, composed of large-scale real-life problems, confirm the efficiency of this procedure.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.publisher Elsevier
dc.relation.isversionof http://hdl.handle.net/10016/10455
dc.rights © Elsevier
dc.title A parallel computation approach for solving multistage stochastic network problems
dc.type article
dc.description.status Publicado
dc.relation.publisherversion http://www.sciencedirect.com/science/article/pii/S0167715200000559
dc.subject.eciencia Estadística
dc.rights.accessRights openAccess
dc.type.version acceptedVersion
dc.identifier.publicationfirstpage 131
dc.identifier.publicationlastpage 160
dc.identifier.publicationtitle Annals of Operations Research
dc.identifier.publicationvolume 90
 Find Full text

Files in this item

*Click on file's image for preview. (Embargoed files's preview is not supported)

This item appears in the following Collection(s)

Show simple item record