Accelerating dual dynamic programming applied to hydrothermal coordination problems

Abstract

Dual Dynamic Programming (DDP) is a decomposition strategy capable of solving high-dimension multistage stochastic optimization problems, which is applied in several fields of study. The DDP method is widely used in hydrothermal coordination planning (HTC) problems for power generation systems - mainly in predominantly hydro power systems, such as in Brazil, Norway and Chile - to define a minimum cost dispatch of power generation, taking into account some uncertainties in the system, such as the natural inflows to the reservoirs. The larger is the system, the more complex is the model, however more expensive is to solve the problem. This work presents new strategies to accelerate DDP method, which consist in local convergence tests in scenario sub-trees, as well as analysis of the stability in the values of state variables along the nodes, to avoid unnecessary forward and backward passes and therefore saving CPU time and memory requirements. Another efficient way to reduce time proposed in this work is a novel asynchronous parallel scheme based on DDP, as well as a partial-asynchronous variant. Such strategies make a better use of the available resources by overcoming some drawbacks of traditional DDP parallel algorithms, which may be too restrictive depending on the structure of the scenario tree. The efficiency of the proposed strategies is shown for a HTC problem of the real large-scale Brazilian system.