Accelerating stochastic capacity expansion planning problems: Temporally split Benders decomposition

Kurzfassung

Stochastic programming is suited to consider uncertainties in energy system optimization models for capacity expansion planning. However, these models become increasingly large and time-consuming to solve, even without considering uncertainties. For two-stage stochastic capacity expansion planning problems, Benders decomposition is often applied to ensure that the problem remains solvable. Since stochastic scenarios can be optimized independently within subproblems, their optimization can be parallelized. However, hourly-resolved capacity expansion planning problems typically have a larger temporal than scenario cardinality. Therefore, we present a temporally split Benders decomposition that further exploits the parallelization potential of stochastic expansion planning problems. A compact reformulation of the storage level constraint into linking variables ensures that long-term storage operation can still be optimized despite the temporal decomposition. The compact formulation requires significantly less storage fixing variables in the master problem compared to previous formulations, especially for stochastic problems. We demonstrate this novel approach with model instances of the German power system with up to 87 million variables and constraints that co-optimize the expansion of generation, transmission and storage technologies. Our results show a reduction in computing times and reduced memory requirements. Additionally, we adapt the algorithm to distributed memory environments in order to exploit the capabilities of high performance computing and systematically implement and analyze the impact of several enhancement strategies, resulting in time savings of up to a factor of 139 compared to classic Benders decomposition.