Fused ultrametric Gromov-Wasserstein for Scenario Tree generation in Multistage Stochastic Programming
Abstract
Multistage Stochastic Programming requires scenario trees that accurately approximate the unknown underlying uncertainty process without violating the non-anticipativity constraint. Most of the existing method for scenario tree generation usually target just one of the two goals at the expense of the other, and just some recent methods try to simultaneously address both. In this paper, we propose to combine two recent distances from Optimal Transport Theory, specifically the ultrametric Gromov-Wasserstein and the Fused Gromov-Wasserstein, into a unique measure to simultaneously deal with the two goals. Our main result is a stability theorem showing that the optimal value of a Multistage Stochastic Programming problem changes by an amount controlled by a Holder-type power of the proposed distance between the true process and its scenario tree approximation, extending Wasserstein-based stability results to control marginal fidelity and non-anticipativity, simultaneously. We propose a block coordinate descent algorithm for the our scenario tree generation based on the proposed distance, and evaluate it on different inventory management test cases.
Related
- Scentree: a framework for generating scenario trees for multistage stochastic programming
- Regret-Based Scenario-Tree Construction for Multistage Stochastic Programs with Deterministic Constraints
- Generalized Wasserstein Flow Matching: Nested Couplings for Point Cloud Generation
- A Note on the NP-Hardness on Quadratic Optimization over Doubly Stochastic Matrices and the Gromov-Wasserstein Problem
- Dynamic programming principle for controlled systems driven by fractional Brownian motions and related backward stochastic Riccati equations
BibTeX
@misc{candelieri2026fused,
title = {{Fused ultrametric Gromov-Wasserstein for Scenario Tree generation in Multistage Stochastic Programming}},
author = {Antonio Candelieri and Iman Seyedi and Francesco Archetti},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.36963},
eprint = {2609.36963},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36963},
}
RIS
TY - UNPB
TI - Fused ultrametric Gromov-Wasserstein for Scenario Tree generation in Multistage Stochastic Programming
AU - Antonio Candelieri
AU - Iman Seyedi
AU - Francesco Archetti
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.36963
UR - https://arxiv.org/abs/2609.36963
AB - Multistage Stochastic Programming requires scenario trees that accurately approximate the unknown underlying uncertainty process without violating the non-anticipativity constraint. Most of the existing method for scenario tree generation usually target just one of the two goals at the expense of the other, and just some recent methods try to simultaneously address both. In this paper, we propose to combine two recent distances from Optimal Transport Theory, specifically the ultrametric Gromov-Wasserstein and the Fused Gromov-Wasserstein, into a unique measure to simultaneously deal with the two goals. Our main result is a stability theorem showing that the optimal value of a Multistage Stochastic Programming problem changes by an amount controlled by a Holder-type power of the proposed distance between the true process and its scenario tree approximation, extending Wasserstein-based stability results to control marginal fidelity and non-anticipativity, simultaneously. We propose a block coordinate descent algorithm for the our scenario tree generation based on the proposed distance, and evaluate it on different inventory management test cases.
ER -