Optimization Online


Stochastic Dynamic Programming Using Optimal Quantizers

Anna Timonina-Farkas(timonina.ann***at***gmail.com)
Georg Pflug(georg.pflug***at***univie.ac.at)

Abstract: 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.

Keywords: multi-stage stochastic optimisation; scenario trees; optimal quantisation; dynamic programming; Kantorovich-Wasserstein distance; inventory control problem; budget allocation problem; natural disasters; floods; risk-management.

Category 1: Applications -- OR and Management Sciences

Category 2: Stochastic Programming

Category 3: Other Topics (Dynamic Programming )

Citation: Available on optimization-online.

Download: [PDF]

Entry Submitted: 10/13/2017
Entry Accepted: 10/13/2017
Entry Last Modified: 10/13/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society