Scenario tree modeling for multistage stochastic programs (Q1016127)

Considered is the multiperiod stochastic program. \[ \min \left\{ \mathbb{E}\left[ \sum\limits_{t=1}^{T}\langle b_{t}\left( \xi _{t}\right) ,x_{t}\rangle \right] \left| \begin{matrix} x_{t}\in X_{t},\qquad \qquad \qquad \qquad \qquad \qquad \qquad \\ x_{t}\text{ is }\mathcal{F}_{t}\left( \xi \right) \text{-measurable,\;} t=1,\dots ,T,\qquad \\ A_{t,0}x_{t}+A_{t,1}\left( \xi _{t}\right) x_{t-1}=h_{t}\left( \xi _{t}\right) ,t=2.\dots ,T \end{matrix} \right. \right\} \leqno(1) \] where the subsets \(X_{t}\) of \(\mathbb{R}^{m_{t}}\) are nonempty and polyhedral, the cost coefficients \(b_{t}\left( \xi _{t}\right) \) belong to \( \mathbb{R}^{m_{t}}\), the right-hand sides \(h_{t}\left( \xi _{t}\right) \) are in \(\mathbb{R}^{n_{t}},\;A_{t,0}\in \mathbb{R}^{n_{t}\times m_{t}}\) are fixed recourse matrices and \(A_{t,1}\left( \xi _{t}\right) \in \mathbb{R} ^{n_{t}\times m_{t-1}}\) technology matrices, respectively. It is assumed that the costs \(b_{t}\left( \cdot \right) \), right-hand sides \(h_{t}\left( \cdot \right) \) and technology matrices \(A_{t,1}\left( \cdot \right) \) depend affinely on \(\xi _{t}\) covering the situation that some of the components of \(b_{t}\) and \(h_{t}\), and of the elements of \(A_{t,1}\) are random. The authors develop (stability) theory-based heuristics for generating scenario trees out of an initial set of scenarios. They establish conditions implying closeness of the optimal values of the original process and its tree approximation, respectively. Also, they give numerical experience for constructing multivariate trees in electricity portfolio management.