Adaptive partition-based SDDP algorithms for multistage stochastic linear programming with fixed recourse

In this paper, we extend the adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse matrix and fixed cost vector to the multistage stochastic programming setting where the stochastic process is assumed to be stage-wise independent. The proposed algorithms integrate the adaptive partition-based strategy with a popular approach for solving multistage stochastic programs, the stochastic dual dynamic programming (SDDP) algorithm, according to two main strategies. These two strategies are distinct from each other in the manner by which they refine the partitions during the solution process. In particular, we propose a refinement outside SDDP strategy whereby we iteratively solve a coarse scenario tree induced by the partitions, and refine the partitions in a separate step outside of SDDP, only when necessary. We also propose a refinement within SDDP strategy where the partitions are refined in conjunction with the machinery of the SDDP algorithm. We then use, within the two different refinement schemes, different tree-traversal strategies which allow us to have some control over the size of the partitions. We performed numerical experiments on a hydro-thermal power generation planning problem. Numerical results show the effectiveness of the proposed algorithms that use the refinement outside SDDP strategy in comparison to the standard SDDP algorithm and algorithms that use the refinement within SDDP strategy.