Evaluation of scenario reduction algorithms with nested distance
- PDF / 1,120,296 Bytes
- 35 Pages / 439.37 x 666.142 pts Page_size
- 26 Downloads / 183 Views
Evaluation of scenario reduction algorithms with nested distance Markéta Horejšová1 · Sebastiano Vitali1,2 Vittorio Moriggia2
· Miloš Kopa1
·
Received: 5 March 2020 / Accepted: 20 July 2020 / Published online: 10 August 2020 © The Author(s) 2020
Abstract Multistage stochastic optimization is used to solve many real-life problems where decisions are taken at multiple times. Such problems need the representation of stochastic processes, which are usually approximated by scenario trees. In this article, we implement seven scenario reduction algorithms: three based on random extraction, named Random, and four based on specific distance measures, named Distance-based. Three of the latter are well known in literature while the fourth is a new approach, namely nodal clustering. We compare all the algorithms in terms of computational cost and information cost. The computational cost is measured by the time needed for the reduction, while the information cost is measured by the nested distance between the original and the reduced tree. Moreover, we also formulate and solve a multistage stochastic portfolio selection problem to measure the distance between the optimal solutions and between the optimal objective values of the original and the reduced tree. Keywords Nested distance · Multistage stochastic optimization · Scenario tree reduction · Nodal clustering Mathematics Subject Classification 90C15 · 60B05 · 62P05
The research was partially supported by Czech Science Foundation Grant 18-05631S, by MIUR ex-60% 2019 sci.resp. V. Moriggia, by MIUR ex-60% 2020 sci.resp. V. Moriggia and by MIUR ex-60% 2020 sci.resp. S. Vitali. Electronic supplementary material The online version of this article (https://doi.org/10.1007/s10287020-00375-4) contains supplementary material, which is available to authorized users.
B
Sebastiano Vitali [email protected]
Extended author information available on the last page of the article
123
242
M. Horejšová et al.
1 Introduction In many real-life problems the parameters characterizing the structure of the future may be uncertain, e.g. the values of price or the level of demand. To solve this type of problem, the literature suggests exploiting the instruments provided by stochastic optimization, see Birge and Louveaux (1997) and Powell (2014). More precisely, we distinguish between single-stage stochastic optimization when only one decision is taken, and multistage stochastic optimization, when the solution is a sequence of decisions over a given span of times, see Shapiro et al. (2009) and Dupaˇcová et al. (2002). To deal with these types of problems, we typically assume that the uncertain parameters are random variables with known probability distribution. This distribution is usually approximated by a discrete distribution represented by a scenario tree. In order to better approximate the initial distribution, the scenario tree may become rather large making the problem computationally intractable. Therefore, several scenario tree reduction algorithms have been proposed in the l
Data Loading...
