Orateur
Description
A central challenge in multi-stage stochastic programs (MSP) lies in constructing scenario trees that approximate the underlying stochastic process with sufficient accuracy while maintaining computational tractability. In this work, we consider the case where the true stochastic process is discretely distributed, and the topology of the approximating scenario tree is fixed.
We propose two novel scenario tree approximation methods grounded in optimal transport theory. The first approach minimizes the stagewise Wasserstein distance between the empirical distributions of the true process and those induced by the scenario tree, ensuring stage-by-stage closeness. The second approach leverages the Fused Gromov-Wasserstein (FGW) distance, which integrates both the feature-level differences (captured by the Wasserstein distance) and structural discrepancies (captured by the Gromov-Wasserstein distance) between distributions. This is particularly suitable for scenario trees, which are structured objects combining probabilistic and topological information.
Both approaches formulate the scenario tree generation as a continuous, nonconvex optimization problem. To solve this, we employ a block coordinate descent method that alternates between optimizing over the discrete distribution assignments and the associated cost structure. This enables efficient computation while preserving fidelity to the underlying stochastic process.
Our methods offer a principled way to balance the trade-off between approximation accuracy and computational feasibility.
