ScenTrees.jl

We present ScenTrees.jl package for generating and improving scenario trees and scenario lattices for multistage stochastic optimization problems using stochastic optimization.

Note: See also the active fork at https://github.com/aloispichler/ScenTrees.jl.

Main features of the package

We provide algorithms for generating and improving scenario trees and scenario lattices for multistage stochastic optimization problems using stochastic approximation. In this package, we use a fixed number of trajectories of a stochastic process to generate and improve a scenario tree or a scenario lattice. The quality of approximation between the stochastic process and the scenario tree/scenario lattice is measured using a multistage (process) distance. The multistage distance suits well to measure the distance between stochastic processes because it takes notice of the effect of evolution of the process over time (cf. Georg Ch. Pflug and Alois Pichler(2012) for more on distances for multistage stochastic optimization models and the multistage distance). The resulting scenario tree/lattice from the stochastic approximation process represents the stochastic process in the best possible way and so can be used for decision making process.
We also provide the user with one of the methods of generating trajectories from an array of data using conditional density estimation. This method takes two steps: First, we use the conditional density estimation to generate new but different samples based on the data given. Here we estimate the distribution of transitional densities given the history of the process via the non-parametric kernel distribution. Finally, we use the composition method to get a sample from the above distribution. The trajectory created in this process can then be used in the stochastic approximation algorithm to generate scenario trees or scenario lattices for multistage stochastic approximation. We urge the user to have a look at Georg Ch. Pflug and Alois Pichler(2016) and Georg Ch. Pflug and Alois Pichler(2015) for the mathematical theory and Seguin Sara et.al(2017) for an earlier exemplary application on an electricity data.

In the following tutorials, we urge the user to be quite familiar with the theory and explanation of the stochastic approximation algorithm in the paper Georg Ch. Pflug and Alois Pichler(2015).

Installation

The package ScenTrees.jl can be installed in Julia REPL as follows:

julia> using Pkg
julia> Pkg.add("ScenTrees")
julia> using ScenTrees

Once you have ScenTrees.jl installed, we recommend that you have a look on the tutorials from the beginning to the end to understand on how you can use the package to generate scenario tree/lattice using stochastic approximation.

Important functions in the package

The following are the most important functions that ScenTrees.jl package provides. These functions are explained in detail in the upcoming tutorials.

Process function: This is a user-specified function that generates trajectories of a stochastic process that the user wants to approximate by a scenario tree or a scenario lattice. To choose whether you are going to approximate with a scenario tree or a scenario lattice depends on the type of stochastic process that you have. Scenario trees are used for discrete-time stochastic processes while scenario lattices are natural discretization of the Markovian processes. This function should return an array in 2 dimension. It should not take any inputs else the user should consider using wrappers or function closures. The array returned by this function should have a length equal to the number of stages of the scenario tree/lattice, as well should have the same dimension as the dimension of the states of nodes of the tree/lattice. The user provides this function to the stochastic approximation process. Examples of inbuilt process functions are gaussian_path1D(), gaussian_path2D(), running_maximum1D(), running_maximum2D(), path().
Tree: This provides the structure of a scenario tree. It stores all the information of a tree. These information includes the name of the tree, the parent of each node, the state of each node and the probabilities from one node to another. An initial tree can be generated by Tree([bstructure],dimension) where bstructure is a vector of the branching structure of the tree and dimension is the dimension of states of nodes in the tree, where dimension = 1 indicates that each node of the tree takes just one value.
Scenario tree approximation: It returns a valuated probability scenario tree that approximates the stochastic process in the best possible way. The function tree_approximation!(Tree([bstructure], dimension), path, nIterations, p=2, r=2) takes: A scenario tree object from the Tree() function with a certain branching structure, a function generating trajectories, number of iterations, choice p of the norm (Example: max = 0, sum = 1, Euclidean = 2 (default)), and multistage distance parameter (r = 2 (default)). The number of iterations also represents the number of trajectories from the process function that we want to improve the scenario tree. For each iteration, we perform the stochastic approximation process which modifies one path in the tree towards the new trajectory and hence the approximating quality of the tree is improved in each iteration.
Scenario lattice approximation: It is used to approximate Markovian processes. As already indicated, scenario lattices are natural discretization of Markov processes. The function lattice_approximation([bstructure], path, nIterations, r = 2, dim = 1) takes: the branching structure of the lattice, function generating trajectories from a stochastic process, the number of iterations, multistage distance parameter r (default r = 2) and the dimension dim which you are working on . The scenario lattice approximation follows the the same procedure as scenario tree approximation but here we find the closest lattice entry and use samples from the process function to improve it.
Generation of scenarios from data: This is a non-parametric technique for generating samples from a given limited data with unknown distribution. We use this process to generate new but different samples based of the data given using the conditional density estimation techniques. The new samples can then be used to generate scenario trees and scenario lattices. The function kernel_scenarios(data, KernelDistribution = Logistic; Markovian = true) takes: 1. A limited two dimensional data (i.e., N x T matrix where N is the number of trajectories and T is the number of stages, 2. Kernel Distribution is the distribution that you want to use for the kernels. The default distribution is Logistic distribution. The user is free to choose any distribution he/she wishes from the package Distributions.jl, and, 3. an optional keyword to determine whether the trajectories generated are Markovian or not. When you set Markovian = true, the trajectories here are Markovian and are used to approximate a scenario lattice. Similarly, if you set Markovian = false, the trajectories are non-Markovian and are to generate scenario trees.