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

This paper proposes and illustrates a novel method for scenario set reduction in multi-stage stochastic programming problems. Reducing the number of scenarios in these problems from many thousands of scenarios to a much smaller number is one way to improve computational tractability. Our proposed method draws from the theory of bipartite graphs and community detection in social networks. The method is particularly well-suited for situations where "scenarios"are both high-dimensional and large in number. A particular contribution of the graph-based method presented in this paper is that it endogenizes the size of the reduced scenario set to optimize a well-defined objective function. We illustrate the graph-based scenario reduction method on a generation expansion planning (GEP) problem from the existing literature. Comparison with other common scenario reduction methods demonstrates that the graph-based method is fast, and yields outcomes consistent with other methods while using a smaller reduced scenario set.