## 5 Dual Bounds by Scenario Decomposition
Maximizing the total distance intra-clusters, we have the following mathematical programming formulation of the maximal diversity in clusters:  
\[\max \sum_{n,s,s^{\prime}}d_{s,s^{\prime}}x_{n,s}x_{n,s^{\prime}} \tag{50}\] \[\forall n, \sum_{s}x_{n,s}\leqslant M\] (51) \[\forall s, \sum_{n}x_{n,s}=1\] (52) \[\forall n,s, x_{n,s}\in\{0,1\} \tag{53}\]  
Objective (50) maximizes the total distance intra-clusters, using a quadratic function in variables \(x_{n,s}\). Contraints (51) bound the cardinal of each subset, to deal with at most \(M\) scenarios. Contraints (52) impose that each scenario is assigned to exactly one subset, to define a partition of the number of scenarios. To solve this last partitioning problem with an MILP solver, we use a standard linearization techniques for quadratic optimization problems with binary variables, introducing new binaries \(y_{n,s,s^{\prime}}\), such that \(y_{n,s,s^{\prime}}=x_{n,s}x_{n,s^{\prime}}\), to have a linear formulation in the space of variables \(x,y\):\[ \begin{array}{llll}\max_{x_{n,s},y_{n,s,s^{\prime}}\in\{0,1\}}&\sum_{n,s,s^{ \prime}}&d_{s,s^{\prime}}y_{n,s,s^{\prime}}\\ \forall n,&\sum_{e}x_{n,s}&\leqslant M\\ \forall s,&\sum_{n}x_{n,s}&=1\\ \forall n,s,s^{\prime}&y_{n,s,s^{\prime}}&\leqslant x_{n,s}\\ \forall n,s,s^{\prime}&y_{n,s,s^{\prime}}&\leqslant x_{n,s^{\prime}}\\ \forall n,s,s^{\prime}&y_{n,s,s^{\prime}}&\geqslant x_{n,s^{\prime}}+x_{n,s}- 1\end{array}  \tag{54}\]  
Such formulation may be inefficient for a straightforward MILP solving with B&B solvers. Here, we need to have a good solution in a reasonable time. When the optimization problem (54) is not easily solvable with an MILP solver, one can design a matheuristic Hill-Climbing (HC) local search. Starting from an initial solution, one consider the optimization problem (54) in local re-optimizations with at most \(2M\) scenarios and two clusters. One can operate the \(N(N-1)/2=O(N^{2})\) optimizations considering all pairs of clusters to define one HC iteration. It is indeed an HC heuristic, each local optimization of (54) furnishing at least the same solution as the current one. Algorithm 1 describes precisely such HC matheuristic. To define an initial partition of scenarios for the local search, one can consider subsets \(\{1,..,M\}\), \(\{M+1,..,2M\}\),..., \(\{(N-1)M+1,..,S\}\), defining trivially a partition of \(\mathcal{S}\) in at most \(N\) subsets containing at most \(M\) scenarios. A better initialization gathers scenarios using a one-dimensional, dispersion problem. Sorting firstly the scenarios of \(\mathcal{S}\) such that the cumulated demands \(\overline{D}_{s}=\frac{1}{t}\sum_{t}\mathbf{D}_{s,t}\) is increasing, i.e., \(s^{\prime}>s\Longrightarrow\overline{D}_{s^{\prime}}\geqslant\overline{D}_{s}\), we can define an initial partition with \(S_{n}=\{s_{aN+n}|a\in N,aN+n\leqslant S\}\). ```
Input: - \(M<S\) the maximal number of scenario in a subset of the partition; - \(d_{s,s^{\prime}}\), the matrix for distances between scenarios \(s\) and \(s^{\prime}\); - nbIter, maximal number of hill climbing iterations; Initialization: - compute \(\overline{D}_{s}=\frac{1}{t}\sum_{t}\mathbf{D}_{s,t}\), \(N=\left\lceil\frac{S}{M}\right\rceil\); - re-index the scenarios such that \(s^{\prime}>s\Longrightarrow\overline{D}_{s^{\prime}}\geqslant\overline{D}_{s}\); - set \(\mathcal{P}_{n}=\mathcal{S}\cap(N\mathbb{Z}+n)\) for \(n\in\llbracket 1;N\rrbracket\) defining an initial partition of \(\mathcal{S}\) ; for it from 1 to nbIter: for\(n=1\) to \(N-1\) : for\(n^{\prime}=n+1\) to \(N\) :  reoptimize subsets \(\mathcal{P}_{n}\), \(\mathcal{P}_{n^{\prime}}\) solving (54) in \(\mathcal{P}_{n}\cup\mathcal{P}_{n^{\prime}}\) with \(M=2\) endfor endfor if no improvement was provided in the last \(N(N-1)/2\) MILP resolutions then break endfor return the partition of \(\mathcal{S}:(\mathcal{P}_{n})_{n\in\llbracket 1;N\rrbracket}\)
```  
**Algorithm 1** Partitioning HC matheuristic to maximize the diversity of scenarios.