Unit commitment (UC) is a key operational problem in power systems used to determine an optimal daily or weekly generation commitment schedule. Incorporating uncertainty in this already difficult mixed integer optimization problem introduces significant computational challenges. Most existing stochastic UC models consider either a two-stage decision structure, where the commitment schedule for the entire planning horizon is decided before the uncertainty is realized, or a multistage stochastic programming model with simplistic stochastic processes to ensure tractability. We propose a new type of decomposition algorithm based on Stochastic Dual Dynamic Integer Programming (SDDiP) to solve a dynamic programming formulation of a multistage stochastic unit commitment (MSUC) problem. We propose a variety of computational enhancements to adapt SDDiP to MSUC, and conduct extensive computational experiments to demonstrate that the proposed method is able to handle elaborate stochastic processes and can solve MSUCs with a huge number of scenarios that are impossible to handle by existing methods.
submitted for publication