Group-and-cut approach for dynamic programming with Fréchet-distributed quantizers

Multi-stage stochastic optimization is a well-known quantitative tool applied in a wide variety of decision-making problems. In this article, we focus on generalized flood risk management problems with Fréchet distributions used to describe the uncertainty. Theoretical solutions of such problems can be found explicitly only in exceptional cases due to their variational form and interdependency of uncertainty in time, e.g., due to cascading impacts of extreme floods. Nevertheless, numerical methods based on Monte Carlo sampling are inaccurate, as the Law of Large Numbers must hold for sufficient approximation quality. To overcome this shortcoming, we introduce an approximation scheme that computes and groups together optimal quantizers of Fréchet distributions. The groups are distinguished by a particular risk threshold and differentiate between higher- and lower-impact floods. We consider optimality of quantization methods in the sense of the minimal Kantorovich–Wasserstein distance. Depending on the group, to which a quantizer belongs, and on the form of the optimization problem, we propose two dynamic programming schemes: with accelerated dynamics and with non-accelerated dynamics. For the accelerated method, the groups of quantizers are used to cut scenario trees and guarantee optimality gaps close to zero. For the non-accelerated method, the probabilities of quantizers are used to weight value functions and bound the approximation error with convergence guarantees. Global solution is guaranteed under convexity and monotonicity conditions on the value functions. Considering cases with and without circular economy indicators able to reduce CO2 emissions, we apply the methods we developed to the governmental budget allocation problem under flood risk in Austria.