Multi-stage stochastic optimization is a well-known quantitative tool for decision-making under uncertainty, which applications include financial and investment planning, inventory control, energy production and trading, electricity generation planning, supply chain management and similar fields. Theoretical solution of multi-stage stochastic programs can be found explicitly only in very exceptional cases due to the complexity of the functional form of the problems. Therefore, the necessity of numerical solution arises. In this article, we introduce a new approximation scheme, which uses optimal quantization of conditional probabilities instead of typical Monte-Carlo simulations and which allows to enhance both accuracy and efficiency of the solution. We enhance accuracy of the estimation by the use of optimal distribution discretization on scenario trees, preserving efficiency of numerical algorithms by the combination with the backtracking dynamic programming. We consider optimality of scenario quantization methods in the sense of minimal Kantorovich-Wasserstein distance at each stage of the scenario tree, which allows to implement both structural and stage-wise information in order to take more accurate decisions for the future, as well as to bound the approximation error. We test efficiency and accuracy of proposed algorithms on the well-known Inventory Control Problem, for which explicit theoretical solution is known, as well as we apply the developed methods to the budget allocation problem for risk-management of flood events in Austria.
Citation
Available on optimization-online.