A parallel computation approach for solving multistage stochastic network problems

This paper presents a parallel computation approach for the efficient solut ion of very large multistage linear and nonlinear network problems with ran dom parameters. These problems result from particular instances of models f or the robust optimization of network problems with uncertainty in the valu es of the right-hand side and the objective function coefficients. The meth odology considered here models the uncertainty using scenarios to character ize the random parameters. A scenario tree is generated and, through the us e of full-recourse techniques, an implementable solution is obtained for ea ch group of scenarios at each stage along the planning horizon. As a consequence of the size of the resulting problems, and the special str ucture of their constraints, these models are particularly well-suited for the application of decomposition techniques, and the solution of the corres ponding subproblems in a parallel computation environment. An augmented Lag rangian decomposition algorithm has been implemented on a distributed compu tation environment, and a static load balancing approach has been chosen fo r the parallelization scheme, given the subproblem structure of the model. Large problems - 9000 scenarios and 14 stages with a deterministic equivale nt nonlinear model having 166000 constraints and 230000 variables - are sol ved in 45 minutes on a cluster of four small (11 Mflops) workstations. An e xtensive set of computational experiments is reported; the numerical result s and running times obtained for our test set, composed of large-scale real -life problems, confirm the efficiency of this procedure.