Scenario Trees and Risk

Electricite de France Humboldt-Universit� zu Berlin
Project director: Prof. Dr. W. Römisch, Humboldt-Universität Berlin, Tel: 030-2093 2561/ Secr. 2353, 

email: romisch@mathematik.hu-berlin.de
Collaborators:  Dipl.-Math. H. Heitsch, Humboldt-Universität Berlin, Tel: 030-2093 5448,  

email: heitsch@mathematik.hu-berlin.de

Dipl.-Math. A. Eichhorn, Humboldt-Universität Berlin, Tel: 030-2093 5448,  

email: eichhorn@mathematik.hu-berlin.de
Company:  EDF Electricite de France   
Period:   December 2003 - May 2004

Aims of the project:

  • Approximation of stochastic programs:
    Presently, a comprehensive methodology is available (see [9]) for studying quantitative stability properties of stochastic programs when approximating the underlying probability distribution. Much is known for two-stage stochastic programming models (with fixed recourse), in particular, the associated probability metrics being relevant for quantitative stability. Much less is known for two-stage models with random recourse and for multi-stage models (without integrality requirements). It is expected that polynomial Fortet-Mourier metrics are relevant in these cases, too.
  • Generation of scenario trees:
    The new technique for generating scenario trees in [4] is based on associated probability metrics. The input of the method consists in a fan of scenarios, i.e., a finite number of simulation scenarios that are provided by the user and, say, obtained from statistical models calibrated to the relevant historical data. Then the method constructs a scenario tree being close to the original fan (w.r.t. the metric) by recursive (optimal) scenario reduction [1], [5]. This technique will be extended and justified. Furthermore, it will be tested on data relevant for the EDF system.
    The scenario reduction approach, forming the basis of the scenario tree generation method, will be extended from using Kantorovich (mass) transportation functionals to Fortet-Mourier metrics. In particular, the backward and forward scenario reduction algorithms of [5] will be extended and, hence, better adapted to the underlying stochastic programming model.
  • Risk modelling and computational issues:
    The expected cost and revenue, respectively, criteria in stochastic power management models may lead to decisions having enormous risk. Hence, suitable risk measure(s) have to be selected to replace the expectation in such models.
    A new subclass of convex risk measures is proposed in [2], namely, so-called polyhedral risk measures and their multiperiod extensions. Polyhedral (multiperiod) risk measures are defined as optimal values of specially structured linear two-stage (multistage) stochastic programs. They are convex (and often coherent) and have the property that by inserting random variables with finitely many scenarios they are polyhedral functions of the scenarios. We develop (dual) representation theorems for such risk measures by relying on stochastic programming theory. In particular, the Conditional Value at Risk CVaR and its multiperiod extensions are polyhedral. Polyhedral risk measures allow
    (1) to maintain the associated probability metrics (of expectation-based models) for stability, and
    (2) the applicability of Lagrangian decomposition approaches with only minor changes in subproblem solvers.

    • Results of the project:

    Results of the project are contained in the papers [3], [6], [7] and [8].

    References:


    [1] J. Dupacova, N. Gröwe-Kuska, W. Römisch: Scenario reduction in stochastic programming: An approach using probability metrics, Mathematical Programming, Ser. A 95 (2003), 493-511.

    [2] A. Eichhorn, W. Römisch: Polyhedral risk measures in stochastic programming, SIAM Journal on Optimization 16 (2005), 69--95.

    [3] A. Eichhorn, W. Römisch, I. Wegner: Mean-risk optimization of electricity portfolios using multiperiod polyhedral risk measures, IEEE St. Petersburg Power Tech 2005.

    [4] N. Gröwe-Kuska, H. Heitsch, W. Römisch: Scenario reduction and scenario tree construction for power management problems, IEEE Bologna Power Tech Proceedings (A. Borghetti, C.A. Nucci, M. Paolone eds.), 2003 IEEE.

    [5] H. Heitsch, W. Römisch: Scenario reduction algorithms in stochastic programming, Computational Optimization and Applications 24 (2003), 187-206.

    [6] H. Heitsch, W. Römisch, C. Strugarek: Stability of multistage stochastic programs, SIAM Journal on Optimization 17 (2006), 511-525.

    [7] H. Heitsch, W. Römisch: Scenario tree modeling for multistage stochastic programs, Mathematical Programming (to appear).

    [8] H. Heitsch, W. Römisch: A note on scenario reduction for two-stage stochastic programs, Operations Research Letters 35 (2007), 731--738.

    [9] W. Römisch: Stability of Stochastic Programming Problems, in: Stochastic Programming (A. Ruszczynski and A. Shapiro eds.), Handbooks in Operations Research and Management Science Vol. 10, Elsevier, Amsterdam 2003, 483-554.

    All papers are downloadable from http://www.mathematik.hu-berlin.de/~romisch/

    last modified December 20, 2007.