# Problem-Driven Scenario Generation for Stochastic Programming Problems: A Survey
## 2 Problem Definition
### Scenario-Tree and Solving Techniques  
In a scenario-tree, each scenario is depicted as a distinct path originating from the tree's root and terminating at one of its leaves. The nodes traversing along each path correspond to the specific values taken by random parameters in the model. When continuous variables are involved, a finite and tractable scenario-tree can be constructed by using sampling  
Figure 1: Illustration of a scenario-tree with 3 stages and 5 scenarios. techniques. A common approach is the Monte Carlo sampling [8; 9; 10]. The sample average approximation (SAA) for the objective function \(f(x)\) can be simply formulated as follows:  
\[\frac{1}{n}\sum_{i=1}^{n}f(x,\xi_{i}). \tag{6}\]  
There are other examples such as quasi-Monte Carlo methods [11], Hidden Markov Models [12], Optimal Quantization [13], Moment-Matching [14], etc. We refrain from providing a detailed discussion of these methodologies in this work. By employing a scenario-tree, the SP problems can be solved with mathematical programming models. Among these approaches, one direct approach is to solve the corresponding Deterministic Equivalent problem. As an illustrative example, we consider a multi-stage SP problem under the assumption that both the constraints and the objective function are linear. Consequently, the multi-stage SP problem defined by (3)-(5) can be reformulated as follows:  
\[\max_{x_{1},\ldots,x_{T}}c_{1}x_{1}+\mathbb{E}_{g}[\sum_{t=2}^{T}c_{t}(\xi_{t} )x_{t}] \tag{7}\]  
s.t. \[A_{1}x_{1}=\mu_{1} \tag{8}\]  
\[B_{t}(\xi_{t})x_{t-1}+A_{t}(\xi_{t})x_{t}=\mu_{t}(\xi_{t}),\quad\forall t\in \{2,\ldots,T\} \tag{9}\]  
\[x_{t}\geq 0,\quad\forall t\in\{1,\ldots,T\}. \tag{10}\]  
By employing a scenario-tree, the stochastic process \(\xi_{t}\) is sampled by a set of \(S\) distinct scenarios. In each scenario \(s\), the function \(c_{t}(\xi_{t})\) in (7) takes a fixed value for each stage \(t\). We denote the decision variable at each stage in each scenario as \(x_{t}^{s}\) and it may assume varying values across different scenarios. The Deterministic Equivalent problem for the problem (7)-(10) is then defined as follows:  
\[\max_{x_{1},x_{2}^{s},\ldots,x_{T}^{s}}c_{1}x_{1}+\sum_{s=1}^{S}p^{s}[c_{s }x_{2}^{s}+\cdots+c_{s,T}x_{T}^{s}] \tag{11}\]  
s.t. \[A_{1}x_{1}=\mu_{1} \tag{12}\]  
\[B_{s,t}x_{t-1}^{s}+A_{s,t}x_{t}^{s}=\mu_{s,t},\quad\forall t\in\{2,\ldots,T\},\forall s\in\{1,\ldots,S\} \tag{13}\]  
\[x_{t}^{s}\geq 0,\quad\forall t\in\{1,\ldots,T\},\forall s\in\{1,\ldots,S\} \tag{14}\]  
\[\frac{1}{n}\sum_{i=1}^{n}f(x,\xi_{i}). \tag{6}\]0  
where \(p^{s}\) is the probability associated with scenario \(s\). Equations (12)-(14) are the constraints defining the feasibility set for the decisions \(x_{t}^{s}\) in each scenario \(s\). Constraint (15) represents the non-anticipativity conditions, which indicates every pair of scenarios \(j\) and \(k\) indistinguishable up to stage \(t\) shares the same decision at stage \(t\) (see Figure 2). In particular, the first stage solution \(x_{1}^{s}\) assumes equal values in all scenarios, i.e., \(x_{1}^{s}=x_{1}\). Through the resolution of the Deterministic Equivalent problem (11)-(15) with each scenario \(s\), it becomes feasible to derive an approximate solution for the original Stochastic Programming problem (7)-(10). Nevertheless, it is essential to note that in this approach, the computational time grows exponentially as the number of scenarios increases. Consequently, solving the Deterministic Equivalent problem becomes infeasible when dealing with a substantial number of scenarios. Given this challenge, decomposition algorithms, such as Lagrangian decomposition [15; 16] and Benders decomposition [5] present more effective alternatives as solving techniques.