## 6 Computational Results
### New Dual Bounds for the Euro/Roadef Challenge 2010  
This section provides our best results, using truncated MILP computations instead of LP+cuts stopping criterion for the most promising schemes. Table 12 presents our best lower bounds and compares it to the former ones [16; 17]. The parameters leading to the reported best dual bounds are presented in Table 12: the MILP relaxation LB or LB(5), the maximal number of scenario in an MILP sub-problem and the maximal time for an MILP computation, time/S denotes the CPU time in seconds per scenario, i.e., an MILP computation considering \(m\) scenarios will be limited to time/S \(\times m\) seconds. In Table 12, OPT in the time/S column denotes that the dual bounds are computed optimally in the 0.001% tolerance gap set for MILP solving with Cplex. The best results for instances A4 and A5 were already given in Table 6. For these instances, the memory space is a limiting factor to reach better dual bounds. For instances A1, A2, and A3, we can compute optimally the LB bounds with 10 scenarios with an accuracy of 0.001%. For instance A1, 10 scenarios correspond to the total number of scenario so that Table 6 gives the best lower bound that we can compute with the LB relaxation, which is also the dual bound that would give the Bender's decomposition from [26]. Our new dual bounds for the datasets B and X improve by more than 0.50% the older ones from the preliminary work [17], which highlights the interest of the partial scenario decomposition and the ML-guided partitioning procedure in Algorithm 1. The most difficult MILP computations are obtained for instances B8 and B9, increasing for instances B8 and B9 the time/S parameter to 3600 s, which was the solving time for the results [17]. Each sub-problem reaches the branching phase which was not the case with time/S = 1800 s. Finishing the cutting planes passes has a significant impact, as already observed in Table 10, but also the \begin{table}
\begin{tabular}{l c c c c c c c} \hline \hline  & [16] & **LB(5)** & **LB** & **LB(5)** & **LB** & **LB(5)** & **LB** \\
**M=** & & **1** & **1** & **2** & **2** & **3** & **3** \\ \hline B6 & 16.58\% & 5.48\% & 5.48\% & 5.26\% & 5.30\% & 5.19\% & 5.26\% \\ B7 & 15.58\% & 6.68\% & 7.99\% & 6.37\% & 7.81\% & 6.28\% & 7.79\% \\ B8 & 23.60\% & 12.41\% & 16.16\% & 12.13\% & 16.23\% & 12.05\% & 16.14\% \\ B9 & 21.72\% & 11.72\% & 15.81\% & 11.47\% & 15.76\% & 11.39\% & 15.70\% \\ B10 & 18.03\% & 7.39\% & 7.53\% & 7.14\% & 7.33\% & 7.05\% & 7.25\% \\ \hline X11 & 15.40\% & 6.17\% & 5.66\% & 5.92\% & 5.42\% & 5.83\% & 5.34\% \\ X12 & 14.22\% & 6.73\% & 6.88\% & 6.43\% & 6.58\% & 6.31\% & 6.50\% \\ X13 & 18.53\% & 8.31\% & 7.82\% & 8.03\% & 7.53\% & 7.93\% & 7.44\% \\ X14 & 17.21\% & 8.06\% & 8.10\% & 7.76\% & 7.81\% & 7.66\% & 7.73\% \\ X15 & 16.83\% & 9.06\% & 9.11\% & 8.74\% & 8.78\% & 8.62\% & 8.69\% \\ \hline Total & 17.80\% & 8.21\% & 9.09\% & 7.94\% & 8.90\% & 7.84\% & 8.83\% \\ \hline \hline \end{tabular}
\end{table} 
Table 11: Dual bounds for datasets B and X, computing of dual bounds LB(5) and LB with LP+cuts computations, aggregation of production time steps and scenario decomposition varying \(M\) the maximal number of scenarios in each sub-problem. first branching operations improve significantly the lower bounds from the root node of the B&B tree in general. This explains the improvement of the lower bounds for instances B8 and B9, from 11.95% and 11.25% in the truncated LP+cuts mode in Table 11, to the final gaps 11.69% and 10.87%. For instances B6, B7, X11, and X12, setting \(\text{time/S}=3600\) s implies an improvement about 0.1%, reaching more advanced phases of the B&B algorithm, whereas the parametrizing \(\text{time/S}=1800\) s allows to reach more than 10,000 nodes in the B&B tree. For the instances of datasets B and X, the memory space is not a limiting factor, and better dual bounds can be obtained allowing more time for the computations of MILP sub-problems.