## 5 Dual Bounds by Scenario Decomposition
: _Let \(\mathcal{S}_{n}\) for \(n\in\llbracket 1;N\rrbracket\) be a partition of \(\mathcal{S}\). We have \(:\sum_{s=1}^{S}v_{\{s\}}\leqslant\sum_{n=1}^{N}v_{\mathcal{S}_{n}}\leqslant v ^{sto}\). In other words, dual bounds for the original problem can be obtained computing dual bounds with a restricted number of scenarios. Considering several scenarios improves the scenario decomposition from [17]._  
**Proof. **\(\sum_{n=1}^{N}v_{\mathcal{S}_{n}}\leqslant v^{sto}\) is proven using Lemma 2 with \(\mathcal{S}^{0}=\mathcal{S}\), and the partition \((S_{n})\), using \(v^{sto}=v_{\mathcal{S}}\) and \(\sum_{\mathcal{S}\in\mathcal{S}}\pi_{s}=1\). Using Lemma 2 for all \(n\in\llbracket 1;N\rrbracket\) with \(\mathcal{S}^{0}=\mathcal{S}_{n}\) and with the partition of \(\mathcal{S}_{n}\) into singletons \(\mathcal{S}_{n}=\bigcup_{s\in\mathcal{S}_{n}}\{s\}\), we have \(\sum_{s\in\mathcal{S}_{n}}v_{\{s\}}\leqslant v_{\mathcal{S}_{n}}\). Summing these \(N\) inequalities, we have: \(\sum_{s=1}^{S}v_{\{s\}}=\sum_{n=1}^{N}\sum_{s\in\mathcal{S}_{n}}v_{\{s\}} \leqslant\sum_{n=1}^{N}v_{\mathcal{S}_{n}}\leqslant v^{sto}=v_{\mathcal{S}}\). \(\square\)  
In [17], only inequality \(\sum_{s=1}^{S}v_{\{s\}}\leqslant v^{sto}\) was proven. Having \(\sum_{s=1}^{S}v_{\{s\}}\leqslant\sum_{n=1}^{N}v_{\mathcal{S}_{n}}\) with Proposition 5 allows for computing better dual bounds considering a restricted number of scenarios. The point is here to maximize the expected dual bound \(\sum_{n=1}^{N}v_{\mathcal{S}_{n}}\) with an appropriate choice of the partition \(\mathcal{S}_{n}\). Supposing that MILP computations of \(v_{\mathcal{S}_{n}}\) are tractable for a given number of scenarios \(M>1\), we focus now on how to choose a partition \(\mathcal{S}_{n}\) with at most \(M\) scenario per subset, while trying to maximize the dual bound \(\sum_{n=1}^{N}v_{\mathcal{S}_{n}}\). Considering conjointly \(M\) identical scenarios, \(v_{\mathcal{S}_{n}}\) computes the optimal maintenance and refueling planning for each scenario, it is the same optimal response for each scenario. Grouping the scenario in (48) induces the same optimal response, and the same dual bound, and it is an equality case in Lemma 2. Similarly, there may exist a very good solution \(x\) common for all the scenarios when similar scenarios are considered, implying a little gap in the inequalities from Lemma 2. To maximize the quality of dual bounds, it is thus preferable to have the most diversified scenarios. Hence, we partition the scenarios in subsets of size at most \(M\), while maximizing the diversity among each subset of scenario. Clustering problems maximizes the similarity inside clusters. To use clustering algorithms, with cardinality constrained versions, we should define a \"distance\" between scenarios \(s,s^{\prime}\) such that \(d_{s,s^{\prime}}\) is higher than scenarios \(s,s^{\prime}\) are similar. Here, we prefer using a distance to measure the similarity of clusters, with \(d_{s,s}=0\), and thus maximizing the diversity in the selected subsets of scenarios. To define such distance, we use the following measure:  
\[\forall s,s^{\prime}\in\mathcal{S},\ \ \ d_{s,s^{\prime}}=\sum_{t\in\mathcal{T}} \left|\mathbf{D}_{s,t}-\mathbf{D}_{s,t^{\prime}}\right| \tag{49}\]  
We use only the power demands to define the dissimilarity between scenarios, assuming it has the most influence in the costs of maintenance planning. The maximal number of scenario per cluster is denoted \(M>0\). Then, \(N=\left\lceil\frac{S}{M}\right\rceil\) is the maximal number of clusters. We define binary variables \(x_{n,s}\in\{0,1\}\), such that \(x_{n,s}=1\) if and only if scenario \(s\in\mathcal{S}\) is included in cluster \(n\in\llbracket 1;N\rrbracket\).