## 3 Computational Experiments
### Second Experimental Campaign: Large Instances  
This experimental campaign is based on the third set of generated instances, a set of random, larger-sized instances, for which it is not possible to obtain the optimal solution by the mathematical model used to solve small instances. These tests permit a better investigation of the behavior of the proposed \(CH\_1 Pa\) algorithm. The obtained results are compared with those of the iterated neighborhood search procedure. In these new sets of instances, the number of nodes ranges from 500 to 5000. For completeness, the following tables report also the results related to small instances. Note that tests have been executed with costs generated uniformly (\([-10,\,10]\), \([-100,\,100]\) and \([1K,\,1K]\)) and with cost structure _P-EL_. Table 3 shows the behavior of \(CH\_1 Pa\) as the size of the instances increases. The number of solutions with objective function values equal to zero is shown. Although we do not know the optimal solution for the generated large instances, obviously we can certify the optimality of the heuristic solution in case a solution with an objective function value equal to zero is identified. We can see that, as the size of the instance increases, the number of zero-solutions improves. The table shows that the proposed algorithm is able to identify 92% of optimal solutions for the solved instances (i.e., 167 on 180) in case of uniform cost distribution in \([-10,10]\). In all instances with a number of nodes greater than or equal to 500, we can obtain the optimal solution. Moreover, with the increase in \(|N|\) also for the distribution of costs _P-EL_ we are able to identify numerous optimal solutions, with \(|N|=5000\) we identify at least 25 optimal solutions (i.e., 83%). \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline  & \multicolumn{3}{c}{\(CHa\)} & \multicolumn{3}{c}{\(CH_1 Pa\)} \\ \cline{2-9}
1N1 & \([\mathbf{-10,10]}\) & \([\mathbf{-100,100]}\) & \([\mathbf{-1K,1K]}\) & _P–EL_ & \([\mathbf{-10,100]}\) & \([\mathbf{-100,100]}\) & \([\mathbf{-1K,1K]}\) & _P–EL_ \\ \hline
100 & 11 & 3 & 1 & 0 & 21 & 8 & 1 & 0 \\
200 & 15 & 3 & 0 & 0 & 26 & 7 & 1 & 1 \\
500 & 24 & 5 & 0 & 0 & 30 & 18 & 3 & 3 \\
1000 & 25 & 14 & 2 & 0 & 30 & 28 & 13 & 6 \\
2000 & 30 & 17 & 2 & 0 & 30 & 30 & 20 & 13 \\
5000 & 30 & 25 & 5 & 0 & 30 & 30 & 27 & 25 \\ \hline
**\#OPT** & **137** & **67** & **10** & **0** & **167** & **121** & **65** & **48** \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Number of optimal solutions identified by \(CHa\) and \(CH\_1 Pa\)—large instances. Table 4 shows the average value of the objective function for the same scenario as Table 3. The data contained in this table are used in Figure 4 to highlight how the solution produced improves as the size increases. Table 5 reports the CPU time in milliseconds. The computational time required to produce a solution using the \(CH\_IPa\) is less than half a second even for instances with 5000 nodes. These computational times suggest that the average number of iterations of the algorithm is significantly less than the number of iterations associated with the computational complexity of the worst case \(O(|N|^{3})\). Table 6 shows the average number of iterations performed by \(IPA\). The \(IOM\) column is useful to understand how many iterations, on average, are performed for every million theoretical iterations associated with the worst case \(O(|N|^{3})\). Figure 5 shows the relationship between the number of iterations and the number of nodes in the graph. For the set of instances used, the trend as \(|N|\) increases appears linear.