danielegioia / scenarioreducer

This library implements several approximate scenario reduction algorithms. Given a probability distribution with finite support, they aim to determine a probability measure with support of reduced and fixed cardinality by selecting the closest to the original one in terms of a selected statistical distance.

ScenarioReducer

This library implements several approximate scenario reduction algorithms. Given a probability distribution with finite support, they aim to determine a probability measure with support of reduced and fixed cardinality by selecting the closest to the original one in terms of a selected statistical distance.

Installation

1. (Recommended) The easiest way to install and use ScenarioReducer is through pip:

       pip install ScenarioReducer

2. (Alternative) You can directly clone the repository

       git clone https://github.com/DanieleGioia/ScenarioReducer.git

Code structure

|____main_example.py
|____scenarioReducer
| |____scenario_reducer.py
| |______init__.py
| |____fast_forward.py
|____tests
| |____test_fast_forward.py

ScenarioReducer Class

It is an abstract class for a scenario reducer that suggests the methods that a scenario reducer should possess. The main method reduce, given a fixed n, must reduce an original set of scenarios with cardinality N to a smaller one of cardinality n.

Different strategies can vary, for example, w.r.t.:

• The statistical distance.
• The selection order (Fast Forward, Backward, Simultaneous Backward, ...).

Fast_forward class

This class implements a scenario reducer that follows a Fast Forward (FF) technique from:

[1] Heitsch, Holger, and Werner Römisch. "Scenario reduction algorithms in stochastic programming." Computational optimization and applications 24.2-3 (2003): 187-206.

FF is preferred for $n\le \frac{N}{4}$ , where $n$ is the new reduced cardinality of the support and $N$ is the original one. For further details please refer to the article.

Example

An easy example to familiarize yourself with the library is provided in main_example.py

Available tests

1. test_fast_forward creates a starting set of one-dimensional Gaussian distributed scenarios of known mean and variance. The test then uses the Fast_Forward class to reduce the number of scenarios. Mean, standard deviation, and 0.05, 0.5, and 0.95 quantiles are eventually compared between the original scenario set and the reduced scenario set to confirm that such statistical measures are close.

scenarioreducer's Issues

How can I know the propability mass shipped from original scenarios to new senarios?

I wanna know the amount of propability mass shipped from $\xi^i$ to $\zeta^j$, represented by $\pi_{ij}$, how can I get it.
I know the problem is as follows

$$\begin{aligned}\min_{\pi\in\mathbb{R}{+}^{n\times m}}&\sum{i=1}^n\sum_{j=1}^m\pi_{ij}|\xi^i-\zeta^j|^2\\text{subject to}&\sum_{j=1}^m\pi_{ij}=p_i,\quad\forall i\in[n],\&\sum_{i=1}^n\pi_{ij}=q_j,\quad\forall j\in[m].\end{aligned}$$

Actually I want to use this method for clustering, and I wanna know the cluster of original scenarios.

How to determine the initial_probs

are the initial_probs all type of time series data is initialized by (1/scenarios_num)*np.ones(scenarios_num)
does the value of initial_probs affect the effect of reduction

Error in algorithm?

Hi! Thank you for sharing your work! It has been a good starting point for scenario reduction for a project I am working on. I think you may have an error in your algorithm. Referencing the Heitsch and Römisch paper, in each step i, it looks like the distance matrix should be updated according to the following rule:

$$c^{[i]}_{ku} := \min \left\{ c^{[i-1]}_{ku}, c^{[i-1]}_{ku_{i-1}} \right\}, k, u \in J^{[i-1]}$$

I don't see that your code does this update. I plan to put together a pull request to address this.

Make package pip installable

@DanieleGioia How would you feel about a PR to make this project pip-installable? That could make it easier for other projects to utilize. I think it just needs some reorganization of files to make it a package and then a pyproject.toml. If you're interested, I'm happy to do the work.