Tree approximation of scenario processes for multistage stochastic optimization: algorithms and fast implementations

For solving multistage stochastic optimization problems it is essential to develop finite approximations of the stochastic process. While the goal is always to find a finite model which represents a given knowledge about the real data process as accurate as possible, the ways of estimating the discrete approximating model may be quite different: (1) if the stochastic model is known as a solution of a stochastic differential equation, e.g., one may generate the scenario tree directly from the specified model; (2) if a simulation algorithm is available, which allows simulating trajectories from all conditional distributions, a scenario tree can be generated by stochastic approximation; (3) if only some observed trajectories of the scenario process are available, the construction of the approximating process can be based on non-parametric conditional density estimates. We also elaborate on the important concept of distances, which allows us to assess the quality of the approximation. We study these methods and apply them to electricity price data. Our fast implementation ScenTrees.jl including an exhaustive documentation is available for free at GitHub (ScenTrees.jl: https://github.com/aloispichler/ScenTrees.jl , cf. Kirui et al. (J Open Sour Softw 5(46):1912, 2020)).