An Efficient Parallel Algorithm for Large Scale Hydrothermal System Operation Planning

This paper presents an efficient parallel algorithm applied to the problem of large scale hydrothermal system operation planning. This problem is solved by stochastic dual dynamic programming. A plan of operation is determined for each stage of the planning period with the objective of minimizing the expected cost of operation over the planning horizon. For each state, the hydrothermal operation problem is modeled as a linear programming problem and the dual variables associated with the solution are used to construct the Benders cuts. The plan of operation is represented by the future cost function, which is approximated by a piecewise linear function, constructed iteratively by the Benders cuts. An optimized parallelization strategy is applied to both the forward and backward cycles of the dynamic programming convergence process with very high parallel efficiency. For a planning horizon of 5 years and 200 inflow scenarios for each reservoir, the sequential solution for the Brazilian system requires almost 15 hours of processing time. The parallel algorithm obtains exactly the same solution in less than 23 min on 64 cores and in less than 17 min on 128 cores.