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.

Automated summary

Managers create scenarios to evaluate the impact of uncertainty on decision making, but the large number of scenarios poses computational challenges. A new approach is proposed to group scenarios based on decisions, using graph clustering to derive groups with mutually acceptable decisions. This method proves effective in deriving high-quality bounds for complex problems under time limitations in stochastic optimization.