(433a) Systematic Methods for Explaining Stochastic Programming Solutions

Stochastic programming (SP) [1] is a powerful approach to modeling optimization problems under uncertainty. However, there is a lack of transparency when it comes to understanding the key factors leading to a particular SP solution, especially when it differs significantly from the solution obtained via deterministic optimization. Conventionally, researchers have developed metrics such as the value of stochastic solution (VSS) and the expected value of perfect information (EVPI) to quantify the superiority of an SP solution over a deterministic one. However, they do not offer any reasoning for why the SP solution performs better. In fact, to the best of our knowledge, there is no systematic methodology for explaining SP solutions whatsoever. As a result, given the complexity of SP formulations, SP solutions are often difficult to understand and hence less trusted by the user, which is a major factor that has prevented its wide application in practice. With an ever-increasing emphasis on accounting for uncertainty in decision making, we believe that a structured explainability paradigm is required to complement the existing SP methodology that can reinforce our confidence in its applicability to real-world problems.

Our work explores the explainability of SP solutions primarily in three dimensions ­­­­­— distributional variations, the impact of recourse variables, and the significance of individual scenarios. In particular, we develop systematic methods for two-stage SP problems to: (1) discover (minimally) perturbed scenario distribution based on metrics such as the Wasserstein distance that yields a desirable alternative solution, (2) devise a ranking system that facilitates dimensionality reduction by providing users with a precise interpretation on which recourse variables have the largest impact on the optimal solution, and (3) evaluate the relative importance of scenarios in affecting the optimal SP solution, in turn devising a scenario reduction technique that filters out the inconsequential scenarios.

Based on the proposed methods, we develop an open-source tool implemented in the Julia programming language [2] that furnishes the explanations to a querying user based on the input two-stage SP model and the pre-specified dimensions of interest. The efficacy of the proposed framework in generating practically meaningful explanations is demonstrated in several computational case studies.

References

[1] Birge, J. R., & Louveaux, F. (2011). Introduction to stochastic programming. Springer Science & Business Media.

[2] Bezanson, J., Edelman, A., Karpinski, S., & Shah, V. B. (2017). Julia: A fresh approach to numerical computing. SIAM review, 59(1), 65-98.