Regret-Based Scenario-Tree Construction for Multistage Stochastic Programs with Deterministic Constraints
Abstract
Scenario trees are widely used to discretize multistage stochastic programs into forms that are tractable for numerical optimization. Yet, traditional scenario-tree construction methods are typically based on statistical similarity between the original uncertainty process and its discretization, and may fail to preserve the aspects of the uncertainty that matter most for decision-making. This paper shows that, under a fixed probability measure and deterministic feasibility constraints, the gap between the optimal value of the original multistage stochastic program and that of its scenario-tree approximation decomposes exactly into a sum of nodewise regret terms, each measuring the optimality loss at a particular node. This decomposition provides a clear target for scenario-tree construction: minimizing total regret across the tree. Motivated by this result, we propose a practical two-phase construction method for repeated stochastic optimization. In an offline phase, computationally inexpensive surrogates for decision regret are learned from data, and in the online phase, these surrogates guide scenario-tree construction. The resulting framework retains the structured optimization and constraint-handling capabilities of multistage stochastic programming while exploiting learned information about the uncertainty to make more effective use of a limited scenario-tree budget. Numerical experiments on multistage stochastic storage and production-planning problems show that, for a fixed tree size, the proposed method constructs higher-quality scenario trees and achieves better closed-loop performance than traditional scenario-tree construction methods.
Related
- Scentree: a framework for generating scenario trees for multistage stochastic programming
- Fused ultrametric Gromov-Wasserstein for Scenario Tree generation in Multistage Stochastic Programming
- Fully Deterministic Shallow Neural Networks with Localized Activations. Part I: Construction and Optimal Sobolev Approximation
- A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints
- Energy conserving compatible space--time FEM for deterministic and stochastic rotating shallow water
BibTeX
@misc{bruneel2026regretbased,
title = {{Regret-Based Scenario-Tree Construction for Multistage Stochastic Programs with Deterministic Constraints}},
author = {Robin Bruneel and Mathijs Schuurmans and Panagiotis Patrinos},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32700},
eprint = {2610.32700},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32700},
}
RIS
TY - UNPB
TI - Regret-Based Scenario-Tree Construction for Multistage Stochastic Programs with Deterministic Constraints
AU - Robin Bruneel
AU - Mathijs Schuurmans
AU - Panagiotis Patrinos
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32700
UR - https://arxiv.org/abs/2610.32700
AB - Scenario trees are widely used to discretize multistage stochastic programs into forms that are tractable for numerical optimization. Yet, traditional scenario-tree construction methods are typically based on statistical similarity between the original uncertainty process and its discretization, and may fail to preserve the aspects of the uncertainty that matter most for decision-making. This paper shows that, under a fixed probability measure and deterministic feasibility constraints, the gap between the optimal value of the original multistage stochastic program and that of its scenario-tree approximation decomposes exactly into a sum of nodewise regret terms, each measuring the optimality loss at a particular node. This decomposition provides a clear target for scenario-tree construction: minimizing total regret across the tree. Motivated by this result, we propose a practical two-phase construction method for repeated stochastic optimization. In an offline phase, computationally inexpensive surrogates for decision regret are learned from data, and in the online phase, these surrogates guide scenario-tree construction. The resulting framework retains the structured optimization and constraint-handling capabilities of multistage stochastic programming while exploiting learned information about the uncertainty to make more effective use of a limited scenario-tree budget. Numerical experiments on multistage stochastic storage and production-planning problems show that, for a fixed tree size, the proposed method constructs higher-quality scenario trees and achieves better closed-loop performance than traditional scenario-tree construction methods.
ER -