Accelerating Dual Dynamic Programming Applied To Hydrothermal Coordination Problems
Autores
|
6615 |
2973,539,1786
|
|
|
6616 |
2973,539,1786
|
|
|
6617 |
2973,539,1786
|
Informações:
Publicações do PESC
A Programação Dinâmica Dual (PDD) é uma estratégia de decomposição capaz de resolver grandes problemas de otimização estocástica multi-estágio, que tem aplicação em diversas áreas de estudo. A PDD é amplamente utilizada no planejamento hidrotérmico de sistemas de energia elétrica, principalmente em sistemas predominantemente hidroelétricos, para definir um despacho de operação de mínimo custo, considerando incertezas em algumas variáveis do problema, notadamente as afluências às usinas hidroelétricas. Quanto maior é o sistema, mais complexo é o modelo que o representa, o que torna mais caro computacionalmente resolver o problema.
Este trabalho apresenta novas estratégias para acelerar o método da PDD, que envolvem um teste de convergência local nas sub-árvores de cenários, assim como uma análise de estabilidade das variáveis de estado, para evitar operações forward e backward - intrínsecas do método de PDD - desnecessárias e economizar tempo de processamento e memória. Outra forma eficiente de redução de tempo proposta neste trabalho é um algoritmo de processamento paralelo assíncrono para a PDD, e uma variante assíncrona parcialmente paralela. Estas estratégias fazem melhor uso dos recursos disponíveis ao contornar algumas restrições de sincronismo da PDD que podem ser muito prejudiciais ao paralelismo. A eficiência das estratégias propostas é mostrada para problemas de planejamento hidrotérmico.
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 in flows 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 eficient 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 eciency of the proposed strategies is shown for a HTC problem of the real large-scale Brazilian system.