Code documentation

Main module mcst

Markov chain scenario trees.

Computes optimally pruned Markov chain scenario trees.

Notes

Uses the polynomial-time algorithm published in [1].

References

[1]	(1, 2) C. Leidereiter, D. Kouzoupis, M. Diehl, A. Potschka, “Fast optimal pruning for Markov chain scenario tree NMPC”, 2019.

mcst.branchwise(tree)

Return sets of nodes and edges from a dict-based tree.

Parameters:tree (dict) – Representation of a scenario tree with as a dictionary with scenario tuple keys and probability values. Returns:

• nodes (set) – Set of nodes of the tree represented by scenario tuples.
• edges (set) – Set of edges of type (nodes[i], nodes[j]) of the tree.

mcst.plot_scenario_tree(tree)

Plot scenario tree.

Parameters:tree (dict) – Representation of a scenario tree with as a dictionary with scenario tuple keys and probability values.

See also

scenario_tree_from_markov_chain()

mcst.prefix_subtree(prefix, node_probs)

Recursively enumerate subtrees preferring larger probabilities.

Recursive generator to enumerate subtrees starting with prefix sorted according to node probabilities node_probs. Used for plotting scenario trees.

Parameters:

• prefix (tuple) – Prefix that characterizes the subtree.
• node_probs (dict) – Contains for each partial scenario the accumulated probabilities of the corresponding subtree.

Yields:

tuple – A scenario of the subtree.

mcst.scenario_tree_from_markov_chain(A, depth, start_state=0, max_scenarios=1000, prob_coverage=0.99, min_scenario_prob=1e-08, interactive_visualization=False, verbose=False, timing=False)

Generate scenario tree from a Markov chain.

A polynomial-time algorithm that enumerates the scenarios of a Markov chain scenario tree of given depth with non-increasing scenario probabilities. The enumeration stops if a maximum number of scenarios has been found, or if the probability coverage of the tree reaches a certain threshold, or if only single scenarios of very small probability are left to be added.

Parameters:

• A ((N,N) ndarray) – Markov chain transition matrix.
• depth (int) – The depth of the scenario tree.
• start_state (int) – The inital state of the Markov chain.
• max_scenarios (int) – The maximum number of returned scenarios.
• prob_coverage (float) – Probability coverage threshold.
• min_scenario_prob (float) – Minimum single scenario probability to consider. All scenarios with smaller probability are discarded immediately. Choosing this parameter wisely can greatly improve the runtime of the algorithm.
• interactive_visualization (bool) – Repeatedly call print_scenario_tree when a new scenario was found.
• verbose (bool) – Print information when a new scenario was found.
• timing (bool) – Measure performance.

Returns:

• tree (dict) – Representation of a scenario tree with as a dictionary with scenario tuple keys and probability values.
• cum_probs ((len(tree),) ndarray) – Cumulative probability (coverage) of the scenarios.
• max_cut_scenario_prob (float) – Maximum of all discarded single scenario probabilities.
• cum_timings ((len(tree),) ndarray) – Only if timing: Cumulative runtime for each computed scenario.

Notes

Uses the polynomial-time algorithm published in [1].

Examples

>>> from scipy.sparse import csr_matrix
>>> A = csr_matrix([[0.875, 0.125], [0.125, 0.875]])
>>> scenario_tree_from_markov_chain(A, depth=3)
({(0, 0, 0, 0): 0.669921875,
  (0, 0, 0, 1): 0.095703125,
  (0, 0, 1, 1): 0.095703125,
  (0, 1, 1, 1): 0.095703125,
  (0, 0, 1, 0): 0.013671875,
  (0, 1, 0, 0): 0.013671875,
  (0, 1, 1, 0): 0.013671875},
 array([0.66992188, 0.765625  , 0.86132812, 0.95703125, 0.97070312,
        0.984375  , 0.99804688]),
 0.0)

Spring packets

Transition matrix for spring packets example.

spring_packets.transition_matrix(N, m, p)

Markov chain transition matrix for chained spring packets.

Parameters:

• N (int) – Number of spring packets
• m (int) – Number of springs per packet.
• p (float) – Failure probability of each single spring.

Returns:

T – Sparse matrix of transition probabilities.

Return type:

((m+1)**(N-1), (m+1)**(N-1)) csr_matrix