Two-stage recombinatory benders decomposition

C.A. Díaz, C.M. Correa-Posada, A. Ramos, J.M. Latorre, D.A. Tejada

14th International Conference on Stochastic Programming - ICSP 2016, Búzios (Brazil). 25 junio - 01 julio 2016

Summary:
The main goal of the power systems planning is the optimal management of the energy resources in order to ensure a safe and reliable operation. Otherwise, the system operation and reliability will be compromised, as happened in Colombian between 1992 and 1993 due to a high dry period. The planning process must be anticipative to the uncertainty, obtaining a solution accounting for multiple future scenarios. This uncertainty is commonly represented by scenario trees [?]. The simultaneous consideration of all the future scenarios usually leads to apply mathematical decomposition techniques due to computational burdensome. The main decomposition techniques are the Benders' decomposition, [?], and the Stochastic Dual Dynamic Programming, [?]. Real applications of these methods have as main disadvantage the strong dependence of the solution on random processes, requiring to reduce the number of scenarios. As a consequence, the robustness of the solution is not guaranteed, especially when draws are made in the early stages of the optimization horizon. The approach presented here has two main characteristics. Firstly, when the forward pass needs draws due to the tree size, they are made as far as possible to the star of the horizon. This decreases the number of stages for the decomposition algorithm, improving the runtimes. Secondly, recombining trees are applied for the uncertainty representation. This improves the backward pass by obtaining more future information to be considered in the previous stages, helping to the convergence speed. This approach is being used for planning the Colombian electric system, showing results consistent with other commercial tools, but with much lower execution times.

Publication date: June 2016.

Citation:
Díaz, C.A., Correa-Posada, C.M., Ramos, A., Latorre, J.M., Tejada, D.A., Two-stage recombinatory benders decomposition, 14th International Conference on Stochastic Programming - ICSP 2016, Búzios (Brazil). 25 June - 01 July 2016.

IIT-16-101A_abstract