A New Multiperiod Stage Definition for the Multistage Benders Decomposition Approach Applied to Hydrothermal Scheduling

Multistage benders decomposition (MSBD), also known as dual dynamic programming, is a well-established technique to solve hydrothermal scheduling problems, especially for predominantly hydro systems. The MSBD methodology solves the problem by iterative forward and backward recursions, approximating the cost-to-go function for each stage by benders cuts, as opposed to traditional dynamic programming approaches that discretize the state space at each time-step. The classical definition of the stages in the MSBD approach is to assign a stage for each time period. In this paper, we propose a new strategy to decompose the problem, where each stage comprises all variables and constraints of several time periods. Numerical results of the application of this strategy to the short- term hydrothermal scheduling problem confirm the advantages of this strategy in terms of CPU time, as compared to the classical stage definition approach. We show that there is an "optimal aggregation factor," which best balances the trade-off between solving a "larger number of shorter subproblems" and solving a "smaller number of larger subproblems." The primal and dual solutions related to different aggregation factors are also compared, and the stability of the results is confirmed. Extensions of the proposed strategy to stochastic problems are discussed.