Subject: Multistage Stochastic Optimization: From Optimal Transport-Based Scenario Tree Reduction to Robust Optimization

Thesis supervisor:  Welington DE OLIVEIRA

Thesis in collaboration with IFP Energies Nouvelles

Abstract: Decision making under uncertainty in multistage stochastic optimization poses a substantial challenge, necessitating a complex trade-off between, on the one hand, the representation of the uncertainties (i.e. the number of scenarios) and, on the other hand, the computational tractability. Scenario reduction methods, pioneered in 2003 by Dupavcova et al., offer a promising outlooks for achieving a satisfactory trade-off. However, the choice of distance metric for reducing scenario trees significantly influences solution quality. While clustering techniques have been prevalent, recent research has turned to Wasserstein-based methods to minimize transport distance between probabilty measures. This work presents a comprehensive investigation of the use of Wasserstein distance for scenario tree reduction in the context of multistage stochastic optimization. The Wasserstein Barycenter (WB) serves as a tool for summarizing sets of probabilities, it appears in a number of disciplines, including applied probability, clustering and image processing. Numerically efficient methods to computing WBs rely on entropic regularization functions, resulting in approximate solutions due to limitations in solver capabilities. In contrast, this research introduces an exact approach based on the Douglas-Rachford splitting method directly applied to the WB linear optimization problem. The proposed solving algorithm achieves a trade-off between the numerical efficiency of regularization-based methods and the precision of exact LP solvers. This thesis also proposes a novel formulation for the unbalanced optimal transport problem. This formulation leads to more flexible real-world applications than literature and the proposed WB method can be easily adapted to tackle unbalanced WB. Another new optimal transport problem is formulated in this thesis: the constraint WB. The motivations is to find WB laying on smaller support or to keep particular properties that can be very useful when performing scenario tree reduction and finds other applications in image processing for example. This work propose exact algorithms to handle this problem. Kovacevic and Pichler developed a reduction algorithm based on nested Wasserstein distance. As we point out in this work, this algorithm consists of computing a significant amount of Wasserstein barycenters. The third contribution of this work is to implement dedicated WB computation algorithms, including the Iterative Bregmann Projection method (IBP) and the newly introduced Method of Averaged Marginals (MAM) in the algorithm proposed by Kovacevic and Pichler 2015 to accelerate its performances. The last contribution of this work is the development of a comprehensive benchmark comparing several optimization frameworks—including reinforcement learning, distributionally robust optimization, and stochastic programming—for solving an industrial-scale multistage energy management problem at IFPEN. We integrate these approaches into a unified software pipeline that encompasses all key components developed in this thesis, including the scenario tree reduction algorithm enhanced by optimal transport techniques.

Key words: Stochastic optimization, Optimal transport, Scenario tree, Mathematical programming, Wasserstein distance, Robust

The defence will be held in English and will also be broadcast live. To receive the connection link, please contact us.