Parallel SDDP

In this project, we consider the Stochastic Dual Dynamic Programming algorithm, commonly used as an approximation method to tackle multistage stochastic decision problems. We present novel techniques that lead to tighter cuts during backward passes in a parallel version of the algorithm, which lead to lower optimality gaps in a shorter amount of time. The aforementioned technique is tested in a hydro scheduling problem for Colombia as well as in an inventory management setting. The implementation is done in Julia using JuMP.

The figure shows a SDDP parallel scheme. Following Curde Dynamic Programing ideas, the value functions are calculated at several points, the points are distributed among available processors.