## 5 Dual Bounds by Scenario Decomposition  
In this section, we face another bottleneck for an efficient MILP solving: the number of scenarios. In the preliminary work [17], it was proven that a decomposition scenario by scenario allows for computing a valid dual bound for the original stochastic problem using \(S\) independent computations with the size of the deterministic problem. This section extends these results, so that a fixed maximal number of scenario can be chosen to group sub-computations. It is proven that generalized scenario decomposition improves the previous decomposition scheme from [17]. Numerical interest in the way of partitioning scenarios is also discussed in this section. We define the following MILP as a general expression for an MILP furnishing dual bounds for the EURO/ROADEF Challenge 2010:  
\[ \begin{split} v^{sto}=&\min_{x\in X,y\geqslant 0}c_{x}x +\sum_{s}c_{s}y_{s}\\ s.t:& Ax\geqslant a\\ \forall s,& Tx+Wy_{s}\geqslant h_{s}\end{split}  \tag{47}\]  
Here, \(x\) denotes the refueling and maintenance planning variables, i.e., \(d_{i,k,w},r_{i,k}\), whereas \(y_{s}\geqslant 0\) gather the other continuous variables indexed by scenarios. Note that matrices \(A\), \(W\), and \(T\) do not depend from \(s\). Let \(\mathcal{S}^{0}\subset\mathcal{S}\). Let \(v_{\mathcal{S}^{0}}\) be the restriction of the MILP \(v^{sto}\) to the subset of scenarios \(\mathcal{S}^{0}\subset\mathcal{S}\):  
\[ \begin{split} v_{\mathcal{S}^{0}}=&\min_{x\in X,y \geqslant 0}\sum_{s\in\mathcal{S}^{0}}\pi_{s}c_{x}x+\sum_{s\in\mathcal{S}^{0}}c_{s} y_{s}\\ s.t:& Ax\geqslant a\\ \forall s\in\mathcal{S}^{0},& T^{1}x+Wy\geqslant h_{s }^{1}\end{split}  \tag{48}\]  
**Lemma 2**. : _Let \(\mathcal{S}^{0}\subset\mathcal{S}\), let \(\mathcal{S}^{0}_{n}\) for \(n\in\llbracket 1;N\rrbracket\) be a partition of \(\mathcal{S}^{0}\), i.e., \(\mathcal{S}^{0}=\bigcup_{n=1}^{N}\mathcal{S}^{0}_{n}\) with \(\mathcal{S}^{0}_{n}\) being disjoint subsets. We have \(\sum_{n=1}^{N}v_{\mathcal{S}^{0}_{n}}\leqslant v_{\mathcal{S}^{0}}\)._  
Proof. : We reformulate \(v_{\mathcal{S}^{0}}\) duplicating variables \(x\) introducing \(x_{s}=x\) for all \(s\in\mathcal{S}^{0}\). Let \(s_{1}\in\mathcal{S}^{0}_{1}\), \(s_{2}\in\mathcal{S}^{0}_{2},\ldots,s_{N}\in\mathcal{S}^{0}_{N}\), and we write such constraints \(x_{s}=x_{s_{n}}(=x)\) for all \(n\in\llbracket 1;N\rrbracket\) and \(s\in\mathcal{S}^{0}\):  
\[ \begin{split} v_{\mathcal{S}^{0}}=\min_{x_{s}\in X,y_{s}\geqslant 0 }&\sum_{s\in\mathcal{S}^{0}}\pi_{s}c_{x}x_{s}+\sum_{s\in \mathcal{S}^{0}}\pi_{s}c_{s}y_{s}\\ s.t:& Ax\geqslant a\\ \forall s\in\mathcal{S}^{0},\forall n\in\llbracket 1;N\rrbracket & x_{s_{n}}=x_{s}\\ \forall s\in\mathcal{S}^{0},& Ax_{s}\geqslant a\\ \forall s\in\mathcal{S}^{0},& Tx_{s}+Wy_{s}\geqslant h _{s}^{1}\end{split} \]  
We get a lower bound for \(v_{\mathcal{S}^{0}}\) relaxing constraints \(x_{s_{n}}=x_{s}\) for all \(n\in\llbracket 1;N\rrbracket\) and \(s\in\mathcal{S}^{0}\) such that \(s\
otin\mathcal{S}^{0}_{n}\). This relaxation implies decoupled and independent sub-problems for each subset \(\mathcal{S}^{0}_{n}\):  
\[ \begin{split} v_{\mathcal{S}^{0}}\geqslant\min_{x_{s},y_{s}}& \sum_{s\in\mathcal{S}^{0}}\pi_{s}c_{x}x_{s}+\sum_{s\in\mathcal{S}^{0}}\pi_{s} c_{s}y_{s}&=\sum_{n=1}^{N}\min_{x_{s_{n}},y_{s}}\sum_{s\in\mathcal{S}^{0} _{n}}\pi_{s}c_{x}x_{s_{n}}+\sum_{s\in\mathcal{S}^{0}_{n}}\pi_{s}c_{s}y_{s}\\ s.t:\forall s\in\llbracket 0;N\rrbracket,& Ax_{s} \geqslant a\\ \forall n\in\llbracket 1;N\rrbracket,&\forall s\in \mathcal{S}^{0}_{n},& x_{s}=x_{s_{n}}& Tx_{s_{n}}+\sum_{w}Wy_{s}\geqslant h_{s}^{1}\\ \forall s\in\mathcal{S}^{0},& Tx_{s}+\sum_{w}Wy_{s} \geqslant h_{s}^{1}\end{split} \]  
The last decoupled optimization problems are \(v_{\mathcal{S}^{0}_{n}}\), so that we have \(\sum_{n=1}^{N}v_{\mathcal{S}^{0}_{n}}\leqslant v_{\mathcal{S}^{0}}\). Lemma 2 guarantees that dual bounds from \(v^{sto}\) can be computed with a fixed number of scenarios, extending the preliminary results from [17]:  
**Proposition 5**.