A graph-theoretic approach to scenario reduction for stochastic generation expansion problems

In operations research and optimization, stochastic programming plays a pivotal role in decision-making under uncertainty. However, solving complex stochastic programs, especially with many scenarios, is computationally challenging. This paper introduces a novel graph-based scenario reduction approach, using bipartite graph theory and community detection algorithms to create a smaller, representative set of scenarios. Unlike many traditional methods, this approach determines the optimal number of scenarios endogenously, improving computational efficiency and robustness. We applied this graph-based method to a two-stage stochastic programming model for power generation expansion planning (GEP), initially comprising 2000 scenarios. Our approach successfully reduced the scenario set while maintaining solution quality. We compare our method with four other techniques-K-means clustering, the Approximate Latent Factor Algorithm (ALFA), Backward Reduction, and Forward Selection. On the GEP problem, the graph-based method yields improved robustness as compared to other methods.