Explaining First-Stage Decisions of Two-Stage Stochastic Programs: Modeling, Reformulations and Solution Methods

Explainability is a growing concern for optimization models used as decision-making tools. It aims to help a stakeholder understand why a model recommends a given outcome, typically by exhibiting the elements of the input that account for this outcome. We study this question for linear two-stage stochastic programs, and explain the returned decision by a small set of scenarios under which it remains optimal. Selecting these scenarios amounts to reweighting the scenario probabilities, and leads to a bilevel model whose lower level is a two-stage stochastic program. We show that a decision can always be explained by at most one more scenario than the number of first-stage variables, whatever the size of the scenario set. We propose three bilevel models that generalize the only previous approach, and solve them with an exact single-level reformulation strengthened by valid inequalities, a decomposition method, and heuristics based on the optimality conditions of the lower level. Computational experiments show the benefits of the bilevel models and of the valid inequalities, which solve a third of the instances that the reformulation alone leaves unsolved. They also show the efficiency of the heuristic based on strong duality, which decides within seconds, on most instances, whether the decision can be explained with a prescribed number of scenarios.

Article

Download

View PDF