#### DMCA

## Evaluation of Scenario-Generation Methods for Stochastic Programming (2003)

Venue: | World Wide Web, Stochastic Programming E-Print Series |

Citations: | 46 - 4 self |

### Citations

1286 |
An Introduction to Copulas
- Nelsen
- 1999
(Show Context)
Citation Context ...st for financial models. On the other hand, a correlation matrix may not be enough to describe the multi-variate structure. In such a case, we may try to match also higher comoments, or use a copula (=-=[26, 4]-=-), if we have the necessary data and a scenario-generation method that can work with these properties. What shall we then do, when we discover that a moment-matching method is either instable or biase... |

340 | Stochastic Programming
- Kall, Wallace
- 1994
(Show Context)
Citation Context ...hese parameters are then described by distributions (in a single-period case), or by stochastic processes (in a multi-period case). A singleperiod stochastic programming model can thus be formulated (=-=[20]) as: &quo-=-t;min" g 0 (x, #) s.t. g i (x, #) # 0, i = 1, . . . , m x # X # R n , (1) where # is a random vector, whose distribution must be independent of the decision vector x. Note that the formulation is... |

122 |
Stochastic decomposition: an algorithm for two-stage linear programs with recourse
- Higle, Sen
- 1991
(Show Context)
Citation Context ...rated scenario tree, some methods for solving stochastic programming problems sample the scenarios during the solution procedure. The most important methods of this type are: stochastic decomposition =-=[14]-=-, importance sampling within Benders' (L-shaped) decomposition [5, 19, 18], and stochastic quasigradient methods [10, 11]. In addition, there are methods that proceed iteratively: they solve the probl... |

105 |
Generating scenario trees for multistage decision problems
- Høyland, Wallace
(Show Context)
Citation Context ...-if the method allows us---other statistical properties (percentiles, higher co-moments, etc). Then we construct a discrete distribution satisfying those properties. Examples of this approach include =-=[32, 30, 24, 15, 22, 25, 12, 16]-=-. Path-based methods. These methods start by generating complete paths, i.e. the scenarios, by evolving the stochastic process { # t }. The result of this step is not a scenario tree, but a set of pat... |

101 |
Scenarios for multistage stochastic programs
- Dupačová, Consigli, et al.
- 2000
(Show Context)
Citation Context ... methods mentioned in Section 2 do not guarantee convergence to the true distribution, but perform very well in real-life problems. For more information on the theoretical properties, see for example =-=[8]. Because -=-of the variety of both scenario-generation methods and decision models, we do not provide a guideline of the type "for this model use that method". Instead, we formulate two important proper... |

90 | Scenario reduction algorithms in stochastic programming
- Heitsch, Römisch
- 2003
(Show Context)
Citation Context ... a scenario subset of prescribed cardinality, and a probability measure based on this set, that is closest to the initial distribution in terms of some probability metrics. The method is described in =-=[9, 29]-=-. 3 9 10 11 12 13 14 18 19 20 21 22 23 24 25 26 0 1 2 3 4 5 15 16 17 6 7 8 Figure 1: Example of a three-period tree Internal sampling methods. Instead of using a pre-generated scenario tree, some meth... |

74 | Scenario tree generation for multiperiod financial optimization by optimal discretization
- Pflug
- 2001
(Show Context)
Citation Context ...enarios have to be clustered (bound) together, in all-butthe -last period. This process is called clustering or bucketing. Examples of these methods can be found in [8, 17]. "Optimal discretizati=-=on". [28]-=- describes a method that tries to find an approximation of a stochastic process (i.e. scenario tree) that minimizes an error in the objective function of the optimization model. Unlike the methods fro... |

73 |
Planning under uncertainty: Solving large-scale stochastic linear programs
- Infanger
- 1994
(Show Context)
Citation Context ...g problems sample the scenarios during the solution procedure. The most important methods of this type are: stochastic decomposition [14], importance sampling within Benders' (L-shaped) decomposition =-=[5, 19, 18]-=-, and stochastic quasigradient methods [10, 11]. In addition, there are methods that proceed iteratively: they solve the problem with the current scenario tree, add or remove some scenarios and solve ... |

71 | Modeling and generation random vectors with arbitrary marginal distributions and correlation matrix.
- Cario, Nelson
- 1997
(Show Context)
Citation Context ...arginal distributions and the correlation matrix. In general, there is no restriction on the marginal distributions, they may even be from different families. Examples of such methods can be found in =-=[2, 24, 6]-=-. Moment matching. The methods from the previous section may be used only if we know the distribution functions of the marginals. If we do not know them, we may describe the marginals by their moments... |

66 |
Russell-Yasuda Kasai model: an asset-liability model for a Japanese insurance company using multi-stage stochastic programming
- Carino, Kent, et al.
- 1994
(Show Context)
Citation Context ...- see [27]. For symmetric distributions, [22] uses an antithetic sampling. Another way to improve a sampling method is to re-scale the obtained tree, to guarantee the correct mean and variance -- see =-=[1]-=-. Sampling from specified marginals and correlations. As mentioned in the previous section, the traditional sampling methods have problems generating multivariate vectors, especially if they are corre... |

58 |
Correlations and Copulas for Decision and Risk Analysis,
- Clemen, Reilly
- 1999
(Show Context)
Citation Context ...st for financial models. On the other hand, a correlation matrix may not be enough to describe the multi-variate structure. In such a case, we may try to match also higher comoments, or use a copula (=-=[26, 4]-=-), if we have the necessary data and a scenario-generation method that can work with these properties. What shall we then do, when we discover that a moment-matching method is either instable or biase... |

57 |
A heuristic for moment-matching scenario generation
- Høyland, Kaut, et al.
- 2003
(Show Context)
Citation Context ...-if the method allows us---other statistical properties (percentiles, higher co-moments, etc). Then we construct a discrete distribution satisfying those properties. Examples of this approach include =-=[32, 30, 24, 15, 22, 25, 12, 16]-=-. Path-based methods. These methods start by generating complete paths, i.e. the scenarios, by evolving the stochastic process { # t }. The result of this step is not a scenario tree, but a set of pat... |

57 | Scenario generation and stochastic programming models for asset liability management
- Kouwenberg
- 2001
(Show Context)
Citation Context ... to improve a sampling algorithm. Instead of a "pure" sampling, we may, for example, use integration quadratures or low discrepancy sequences, if appropriate -- see [27]. For symmetric distr=-=ibutions, [22]-=- uses an antithetic sampling. Another way to improve a sampling method is to re-scale the obtained tree, to guarantee the correct mean and variance -- see [1]. Sampling from specified marginals and co... |

56 |
Monte Carlo (importance) sampling within a Benders decomposition algorithms for stochastic linear programs
- Infanger
- 1992
(Show Context)
Citation Context ...g problems sample the scenarios during the solution procedure. The most important methods of this type are: stochastic decomposition [14], importance sampling within Benders' (L-shaped) decomposition =-=[5, 19, 18]-=-, and stochastic quasigradient methods [10, 11]. In addition, there are methods that proceed iteratively: they solve the problem with the current scenario tree, add or remove some scenarios and solve ... |

45 | The scenario generation algorithm for multistage stochastic linear programming
- Casey, Sen
- 2005
(Show Context)
Citation Context ...ve some scenarios and solve the problem again. Hence, at least in principle, the scenarios are added exactly where needed. The methods differ in the way they decide where to add/remove the scenarios: =-=[3] uses dual-=- variables from the current solution, while [7] measures the "importance of scenarios" by EVPI (expected value of perfect information). 3 Notation and terminology Throughout the paper, we us... |

44 |
Simulating multivariate nonnormal distributions.
- Vale, Maurelli
- 1983
(Show Context)
Citation Context ...-if the method allows us---other statistical properties (percentiles, higher co-moments, etc). Then we construct a discrete distribution satisfying those properties. Examples of this approach include =-=[32, 30, 24, 15, 22, 25, 12, 16]-=-. Path-based methods. These methods start by generating complete paths, i.e. the scenarios, by evolving the stochastic process { # t }. The result of this step is not a scenario tree, but a set of pat... |

35 |
Moment Methods for Decision Analysis,”
- Smith
- 1993
(Show Context)
Citation Context |

30 |
An approximate method for sampling correlated random variables from partially-specified distributions
- Lurie, Goldberg
- 1998
(Show Context)
Citation Context ...arginal distributions and the correlation matrix. In general, there is no restriction on the marginal distributions, they may even be from different families. Examples of such methods can be found in =-=[2, 24, 6]-=-. Moment matching. The methods from the previous section may be used only if we know the distribution functions of the marginals. If we do not know them, we may describe the marginals by their moments... |

30 | CVaR models with selective hedging for international asset allocation,
- Topaloglou, Vladimirou, et al.
- 2002
(Show Context)
Citation Context ...entially with the dimension of the random vector: if we sample s scenarios for k marginals, we end-up with s k scenarios. Another problem is how to get correlated random vectors -- a common approach (=-=[23, 13, 31]-=-) is to find the principal components (which are independent by definition) and sample those, instead of the original random variables. This approach has the additional advantage of reducing the dimen... |

25 |
Scenario reduction in stochastic programming.
- Dupacova, Growe-Kuska, et al.
- 2003
(Show Context)
Citation Context ... a scenario subset of prescribed cardinality, and a probability measure based on this set, that is closest to the initial distribution in terms of some probability metrics. The method is described in =-=[9, 29]-=-. 3 9 10 11 12 13 14 18 19 20 21 22 23 24 25 26 0 1 2 3 4 5 15 16 17 6 7 8 Figure 1: Example of a three-period tree Internal sampling methods. Instead of using a pre-generated scenario tree, some meth... |

24 | EVPI-based importance sampling solution proceduresfor multistage stochastic linear programmeson parallel MIMD architectures.
- Dempster, Thompson
- 1999
(Show Context)
Citation Context ...least in principle, the scenarios are added exactly where needed. The methods differ in the way they decide where to add/remove the scenarios: [3] uses dual variables from the current solution, while =-=[7] measures -=-the "importance of scenarios" by EVPI (expected value of perfect information). 3 Notation and terminology Throughout the paper, we use the following conventions: stochastic variables are den... |

21 |
The Performance of Stochastic Dynamic and Fixed Mix Portfolio Models
- Fleten, Hoyland, et al.
- 2002
(Show Context)
Citation Context ... . . , n1 , since the scenarios do not coincide. In fact, the true problem may even have infinitely many scenarios. The problem can be solved by the rolling horizon approach, described for example in =-=[12]-=-. With our notation, the evaluation of the objective function can be described by an iterative process. For easier understanding, we state only a two period version here, and we assume that also the t... |

16 |
Generating market risk scenarios using principal component analysis: methodological and practical consideraions. Manuscript, Federal Reserve Board.
- Loretan
- 1997
(Show Context)
Citation Context ...entially with the dimension of the random vector: if we sample s scenarios for k marginals, we end-up with s k scenarios. Another problem is how to get correlated random vectors -- a common approach (=-=[23, 13, 31]-=-) is to find the principal components (which are independent by definition) and sample those, instead of the original random variables. This approach has the additional advantage of reducing the dimen... |

12 |
M.: Integration quadratures in discretization of stochastic programs. Stochastic Programming E-Print Series
- Pennanen, Koivu
- 2002
(Show Context)
Citation Context ...scenarios. 2 There are several ways to improve a sampling algorithm. Instead of a "pure" sampling, we may, for example, use integration quadratures or low discrepancy sequences, if appropria=-=te -- see [27]-=-. For symmetric distributions, [22] uses an antithetic sampling. Another way to improve a sampling method is to re-scale the obtained tree, to guarantee the correct mean and variance -- see [1]. Sampl... |

11 |
Methods of Stochastic Programming
- Ermoliev
- 1976
(Show Context)
Citation Context ...n procedure. The most important methods of this type are: stochastic decomposition [14], importance sampling within Benders' (L-shaped) decomposition [5, 19, 18], and stochastic quasigradient methods =-=[10, 11]-=-. In addition, there are methods that proceed iteratively: they solve the problem with the current scenario tree, add or remove some scenarios and solve the problem again. Hence, at least in principle... |

9 |
Stochastic quasigradient methods for optimization of discrete event systems
- Ermoliev, Gaivoronski
- 1992
(Show Context)
Citation Context ...n procedure. The most important methods of this type are: stochastic decomposition [14], importance sampling within Benders' (L-shaped) decomposition [5, 19, 18], and stochastic quasigradient methods =-=[10, 11]-=-. In addition, there are methods that proceed iteratively: they solve the problem with the current scenario tree, add or remove some scenarios and solve the problem again. Hence, at least in principle... |

7 |
Optimization and simulation approaches to scenario tree generation
- Gulpinar, Rustem, et al.
- 2004
(Show Context)
Citation Context |

6 | Stability analysis of a portfolio management model based on the conditional value-at-risk measure,”
- Kaut, Vladimirou, et al.
- 2003
(Show Context)
Citation Context ...e) was generated by a method based on principal component analysis described in [31]. The benchmark tree has 20, 000 scenarios, and is based on data in the period from January 1990 to April 2001. See =-=[21]-=- for a detailed description of properties of the benchmark scenario set. We note that the scenarios of the benchmark tree are not equiprobable. Based on the benchmark tree, we compute the moments and ... |

4 | Modeling and generating multivariate time series with arbitrary marginals and autocorrelation structures.
- Deler, Nelson
- 2001
(Show Context)
Citation Context ...arginal distributions and the correlation matrix. In general, there is no restriction on the marginal distributions, they may even be from different families. Examples of such methods can be found in =-=[2, 24, 6]-=-. Moment matching. The methods from the previous section may be used only if we know the distribution functions of the marginals. If we do not know them, we may describe the marginals by their moments... |

3 |
Scenario Trees for Inflow Modelling in Stochastic Optimization for Energy Planning
- Halldin
- 2002
(Show Context)
Citation Context ...entially with the dimension of the random vector: if we sample s scenarios for k marginals, we end-up with s k scenarios. Another problem is how to get correlated random vectors -- a common approach (=-=[23, 13, 31]-=-) is to find the principal components (which are independent by definition) and sample those, instead of the original random variables. This approach has the additional advantage of reducing the dimen... |

1 |
Dantzig and Gerd Infanger. Large-scale stochastic linear programs—importance sampling and Benders decomposition
- George
- 1991
(Show Context)
Citation Context ...g problems sample the scenarios during the solution procedure. The most important methods of this type are: stochastic decomposition [14], importance sampling within Benders' (L-shaped) decomposition =-=[5, 19, 18]-=-, and stochastic quasigradient methods [10, 11]. In addition, there are methods that proceed iteratively: they solve the problem with the current scenario tree, add or remove some scenarios and solve ... |

1 |
IBM Optimization Library Stochastic Extensions Users Guide
- Corp
- 1998
(Show Context)
Citation Context ...rm a fan to a scenario tree, the scenarios have to be clustered (bound) together, in all-butthe -last period. This process is called clustering or bucketing. Examples of these methods can be found in =-=[8, 17]. "Op-=-timal discretization". [28] describes a method that tries to find an approximation of a stochastic process (i.e. scenario tree) that minimizes an error in the objective function of the optimizati... |

1 | A method to generate multivariate data with moments arbitrary close to the desired moments. Working paper 481
- Lyhagen
- 2001
(Show Context)
Citation Context |

1 |
Scenario tree generation as a multidimensional facility location problem
- Pflug
- 2002
(Show Context)
Citation Context ...io trees. The overview is by no means complete, there are for example many problem-tailored methods. In addition, all the presented methods exist in different flavours. For alternative overviews, see =-=[9, 16]-=-. 2.1 “Pure” scenario-generation methods Conditional sampling. These are the most common methods for generating scenarios. At every node of a scenario tree, we sample several values from the stochasti... |

1 |
Scenario generation for multi-stage decision models: an apporach based on multidimensional facility location
- Pflug, Hochreiter
- 2003
(Show Context)
Citation Context ..., with the given data, produces scenario trees passing the stability tests for the given optimization problem. In our view, such tests should always be performed. Som methods, such as the method from =-=[30, 31]-=-, are not stochastic by nature, so we cannot run the stability tests directly as presented in Section 5. What we could do instead of generating the same tree several times is to vary the size of the t... |