## 6 Computational Results
### Lower Bounds for Datasets B and X
#### 6.5.1 Dual Bounds Computable in Less Than One Hour  
In this section, we focus on dual bounds that can be obtained in less than one hour for datasets B and X, as in [16]. One hour is reasonable for the real-life application, we note that computing separately dual bounds from a primal heuristic is helpful to detect that primal solutions have a prohibitive cost. Figure 1: Demand profiles for the 30 stochastic scenarios of instance A5. Using MILP formulations \(LB(k_{0})\) with \(k^{0}\leqslant 2\), one obtain our quickest computations of dual bounds with MILP sub-problems dealing with a single scenario (\(M=1\)). Such bounds and the computation times are reported in Tables 7 and 8 with respectively LP+cuts and MILP computations. With \(k_{0}=0\) and \(M=1\), \(LB(k_{0})\) problems are solved to optimality as MILPs, and the solving time is, on average, around 200 s for the total measured time. Such lower bounds have a comparable quality to the best bounds from [16]. However, the computation times are not reported precisely in [16]. It is only mentioned that solving the flow-network for all scenarios takes up to an hour for the biggest instances. The quickest lower bounds from [16] are reported with the column [16].1 in Tables 7 and 9 and have a poor quality, but the solving times are computed in less than 10 s. Our approaches cannot provide dual bounds in such restricted times with sequential implementations, using MILP distributed computations with MPI, the dual bounds in Tables 7 and 8 with \(LB(0)\), and \(M=1\) can be computed in less than 20 s.  
Table 7 shows that \(LB(1)\) lower bounds with \(M=1\) and MILP computations outclass significantly the dual bounds from [16], requiring less than one hour computations. Tables 7 and 8 illustrate that computation times differ among the different instances. B8 and B9 are also the most difficult instances for the computations of \(LB(k_{0})\) with \(k_{0}\leqslant 3\). B6,B7, X10, and X11 instances have the quickest computation time, and this is due to their minimal number of stochastic scenarios, as shown in Table 5. Generally, the LP+cuts computations of root node of the B&B tree, as in Table 9, induce a little degradation of the lower bounds with full MILP computations presented in Table 7, for a significant speed up comparing the computational times in both result tables. In a defined time limit, it is more efficient to increase the value \(k\) than reaching more advanced phases in the B&B algorithm. \begin{table}
\begin{tabular}{l c c c c c c c c} \hline \hline  & [16].1 & [16].2 & LB(1) & LB(1) & LB(1) & LB(2) & LB(2) & LB(3) & LB(3) \\  & **Gap** & **Gap** & **t(s)** & **Gap** & **t(s)** & **Gap** & **t(s)** & **Gap** \\ \hline B6 & 56.44\% & 16.58\% & 99 & 14.95\% & 210 & 11.74\% & 419 & 11.67\% \\ B7 & 52.86\% & 15.58\% & 86 & 13.40\% & 310 & 11.18\% & 954 & 11.16\% \\ B8 & 65.32\% & 23.60\% & 811 & 20.34\% & 4485 & 17.37\% & 17.1k & 16.92\% \\ B9 & 63.30\% & 21.72\% & 911 & 18.78\% & 4415 & 15.83\% & 19k & 15.36\% \\ B10 & 60.92\% & 18.03\% & 283 & 16.47\% & 650 & 13.43\% & 1308 & 13.42\% \\ \hline X11 & 57.81\% & 15.40\% & 116 & 12.91\% & 257 & 11.18\% & 472 & 11.07\% \\ X12 & 52.65\% & 14.22\% & 118 & 12.29\% & 257 & 10.30\% & 574 & 10.28\% \\ X13 & 66.20\% & 18.53\% & 315 & 16.01\% & 832 & 14.28\% & 1662 & 14.11\% \\ X14 & 64.67\% & 17.21\% & 344 & 14.95\% & 926 & 13.23\% & 1761 & 13.11\% \\ X15 & 61.76\% & 16.83\% & 376 & 16.13\% & 756 & 13.52\% & 1378 & 13.49\% \\ \hline Total & 60.15\% & 17.80\% & 3458 & 15.64\% & 7.6k & 13.22\% & 42.6k & 11.65\% \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Comparing with [16] the dual bounds using LP+cuts computations of \(LB(k_{0})\) with \(k_{0}<3\).