Decision-based scenario clustering for decision-making under uncertainty

In order to make sense of future uncertainty, managers have long resorted to creating scenarios that are then used to evaluate how uncertainty affects decision-making. The large number of scenarios that are required to faithfully represent several sources of uncertainty leads to major computational challenges in using these scenarios in a decision-support context. Moreover, the complexity induced by the large number of scenarios can stop decision makers from reasoning about the interplay between the uncertainty modelled by the data and the decision-making processes (i.e., how uncertainty affects the decisions to be made). To meet this challenge, we propose a new approach to group scenarios based on the decisions associated to them. We introduce a graph structure on the scenarios based on the opportunity cost of predicting the wrong scenario by the decision maker. This allows us to apply graph clustering methods and to obtain groups of scenarios with mutually acceptable decisions (i.e., decisions that remain efficient for all scenarios within the group). In the present paper, we test our approach by applying it in the context of stochastic optimization. Specifically, we use it as a means to derive both lower and upper bounds for stochastic network design models and fleet planning problems under uncertainty. Our numerical results indicate that our approach is particularly effective to derive high-quality bounds when dealing with complex problems under time limitations.