# Problem-Driven Scenario Generation for Stochastic Programming Problems: A Survey
## 4 Problem-Driven Scenario Generation
### Methodologies
\begin{table}
\begin{tabular}{c c c} \hline
**Paper** & **Cat.** & **Example Problem** \\ \hline [PERSON] and [PERSON] [47] & SA & Asset allocation \\ [PERSON] and [PERSON] [48] & GSG & Stochastic unit commitment \\ [PERSON] and [PERSON] [49] & GSG & Facility layout problem \\ [PERSON] et al. [50] & GSG & Transmission network expansion planning \\ [PERSON] and [PERSON] [51] & FFO & Stochastic knapsack problem \\ [PERSON] et al. [52] & FFO & Portfolio selection with tail risk measures \\ [PERSON] et al. [53] & FFO & Portfolio selection with tail risk measures \\ [PERSON] et al. [54] & GSG & Stochastic vehicle routing problem \\ [PERSON] and [PERSON] [30] & SA & Stochastic knapsack problem \\ [PERSON] [46] & SA & Air traffic flow management \\ [PERSON] et al. [55] & SRC & Network design/Facility location \\ [PERSON] and [PERSON] [56] & SRC & The news-vendor problem \\ [PERSON] et al. [57] & SRC & Biweekly fleet planning/Network design \\ [PERSON] and [PERSON] [58] & SRC & Portfolio optimization/Aircraft allocation/ \\  & & Electric power extension planning \\ [PERSON] et al. [59] & SRC & Network design/Multidimensional news-vendor/Air- \\  & & lift operations scheduling/Storage layout and routing \\ \hline \end{tabular}
\end{table} 
Table 1: Literature on problem-driven scenario generation chronologically. by a low likelihood of occurrence, but holds a considerably high value when it occurs. In real-world problems, tail risk refers to the probability of infrequent and exceptional events taking place, often leading to substantial losses or disruptions. For example, in the work of [53], the conditional expectation of the random variable above its \(\beta\)-quantile is evaluated, which is also referred to as the Conditional Value at Risk (CVaR) [64], which evaluates the expected loss in the event that the worst-case threshold is crossed:  
\[\beta\text{-CVaR}(\theta)=\frac{1}{1-\beta}\int_{\beta}^{1}F_{\theta}^{-1}(u )du, \tag{16}\]  
with \(\theta\) being a random variable with distribution functions \(F_{\theta}\) and \(0<\beta<1\). The objective of the corresponding SP problem is to find the optimal decision that minimizes the value of \(\beta\text{-CVaR}\). Given that the tail risk is conceptualized as a function of a random variable that only depends on the upper tail of its distribution function, the value of any tail risk measure in the corresponding SP problems depends only on scenarios that are restricted within a defined region referred to as the risk region. In such a case, it has been demonstrated by [53] that problem-driven scenario generation methodologies consistently produce better and more stable solutions compared to standard Monte Carlo sampling. The methodologies for problem-driven scenario generation function in the following manner: with aggregation sampling, a predetermined quantity of scenarios are supposed to be in the risk region. The algorithm randomly selects samples from the distribution, storing only those samples that lie in the risk region, while aggregating those outside the risk region into a single point, usually their average value. The algorithm terminates once the predetermined number of risk scenarios has been attained. The method has been validated on the portfolio selection problem in [52]. While the aforementioned methodologies realize problem-driven scenario generation by explicitly considering the problem's features, a scenario generation process based only on the out-of-sample performance with heuristic solutions is proposed in [30]. It is realized by formulating a loss function that quantifies the discrepancy between the out-of-sample and in-sample performance of the given solutions (see Section 3.1). By minimizing the loss function for a specified number of scenarios, the scenario-tree generation process can be expressed as follows:  
Figure 5: Example of a tail risk distribution. * Initiate the process by generating a pool of solutions \(x_{i}\) with \(i\in\{1,\ldots,n\}\), using a heuristic approach that strikes an appropriate balance between speed and accuracy.