Scenario tree construction driven by heuristic solutions of the optimization problem
- PDF / 1,127,420 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 15 Downloads / 138 Views
Scenario tree construction driven by heuristic solutions of the optimization problem Vit Prochazka1,2 · Stein W. Wallace1 Received: 4 November 2019 / Accepted: 10 April 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We present a new scenario generation process approach driven purely by the out-ofsample performance of a pool of solutions, obtained by some heuristic procedure. We formulate a loss function that measures the discrepancy between out-of-sample and in-sample (in-tree) performance of the solutions. By minimizing such a (usually non-linear, non-convex) loss function for a given number of scenarios, we receive an approximation of the underlying probability distribution with respect to the optimization problem. This approach is especially convenient in cases where the optimization problem is solvable only for a very limited number of scenarios, but an out-of-sample evaluation of the solution is reasonably fast. Another possible usage is the case of binary distributions, where classical scenario generation methods based on fitting the scenario tree and the underlying distribution do not work. Keywords Stochastic optimization · Scenario tree · Scenario generation
1 Introduction Most methods for solving stochastic programs require discrete scenarios as input. Exceptions would be simple (often inventory) models that have closed-form solutions and methods such as stochastic decomposition (Higle and Sen 1991), where the discretization takes place inside the method. The simplest way to find scenarios that can be used as input is normally to sample (Cario and Nelson 1997; Lurie and Goldberg 1998). If sampling leads to numerically solvable problems with high enough
B
Vit Prochazka [email protected] Stein W. Wallace [email protected]
1
Department of Business and Management Science, NHH Norwegian School of Economics, Helleveien 30, Bergen, Norway
2
SNF – Centre for Applied Research at NHH, Helleveien 30, Bergen, Norway
123
V. Prochazka, S. W. Wallace
accuracy in short enough time [see for example the discussion in Kaut et al. (2007)], there is no good reason to do anything more complicated. But, if for some reason, sampling is not acceptable, there is a need for something more advanced—and most likely more computationally challenging. Very often, the alternatives require some rather expensive offline computations, but lead to a much more efficient online performance. For an overview, see for example King et al. (2012). The methods fall into two major classes; those that try to approximate the probability distribution itself, and those that focus on the quality of the solutions that emerge from using the scenarios. We can call these methods distribution-oriented and problem-oriented. Both use a metric to measure distance, the first uses measures from probability theory (such as the Kantorovich–Rubinstein or Wasserstein metric Pflug 2001), the second uses the optimization problem itself as metric. This paper falls into the second category, and is hence connected to the princip
Data Loading...
