# Solution Algorithms for the Capacitated Location Tree Problem with Interconnections
## 5 Computational Experiments
This was expected since exact algorithms struggle with large test instances because the number of possible solutions grows exponentially. The average solution time for all test instances was 5221.63 s. For instances with 36 clients or fewer, the exact method found the optimal solution in less than 2 min except for the instance \"coordGaspelle32-5b.dat\", which required 529.44 s. For instances with 50 or more clients, the EM could not find the optimal solutions in 7200.00 s, although it found near-optimal quality solutions for instances with up to 100 clients. The EM sometimes surpassed the 7200.00 s limit due to the nature of the branch-and-bound procedure and the required time to retrieve the final LB and UB solutions. \begin{table}
\begin{tabular}{c r r r r} \hline \hline
**Instances** & **LB** & **UB** & **Gap** & **T16** \\ \hline coord20-5-1.dat & 21,327.37 & 21,327.68 & 0.00 & 10.92 \\ coord20-5-1b.dat & 15,638.81 & 15,638.81 & 0.00 & 4.97 \\ coord20-5-2.dat & 22,893.29 & 22,893.29 & 0.00 & 5.08 \\ coord20-5-2b.dat & 14,050.44 & 14,051.02 & 0.00 & 3.15 \\ coord50-5-1.dat & 15,219.37 & 15,262.86 & 0.29 & 7200.64 \\ coord50-5-1b.dat & 15,065.81 & 15,098.14 & 0.21 & 7200.64 \\ coord50-5-2.dat & 29,563.77 & 29,582.63 & 0.06 & 7200.64 \\ coord50-5-2b.dat & 29,520.52 & 29,580.44 & 0.20 & 7200.64 \\ coord50-5-2 BIS.dat & 16,845.06 & 16,869.25 & 0.14 & 7200.63 \\ coord50-5-2 bIS.dat & 17,836.50 & 17,879.67 & 0.24 & 7200.64 \\ coord50-5-3.dat & 11,099.39 & 11,135.09 & 0.25 & 7200.64 \\ coord50-5-3b.dat & 10,973.95 & 11,005.12 & 0.28 & 7200.64 \\ coord100-5-1.dat & 133,473.45 & 133,544.83 & 0.05 & 7200.72 \\ coord100-5-1b.dat & 133,255.56 & 133,320.51 & 0.05 & 7200.71 \\ coord100-5-2.dat & 97,292.59 & 97,352.20 & 0.06 & 7200.69 \\ coord100-5-2b.dat & 97,075.44 & 97,114.30 & 0.04 & 7200.70 \\ coord100-5-3.dat & 86,829.41 & 86,878.30 & 0.06 & 7200.71 \\ coord100-5-3b.dat & 86,630.17 & 86,683.47 & 0.06 & 7200.70 \\ coord100-10-1.dat & 155,463.85 & 155,564.86 & 0.06 & 7200.72 \\ coord100-10-1b.dat & 155,299.63 & 155,357.72 & 0.04 & 7200.72 \\ coord100-10-2.dat & 141,492.96 & 141,570.05 & 0.05 & 7200.74 \\ coord100-10-2b.dat & 141,354.23 & 141,416.36 & 0.04 & 7200.68 \\ coord100-10-3.dat & 136,552.56 & 139,911.96 & 2.46 & 7200.84 \\ coord100-10-3b.dat & 136,412.67 & 136,486.56 & 0.05 & 7200.84 \\ coord200-10-1.dat & 232,017.92 & 338,024.89 & 45.69 & 7212.86 \\ coord200-10-1b.dat & 231,458.68 & 318,817.21 & 37.74 & 7201.71 \\ coord200-10-2.dat & 261,216.53 & 339,855.34 & 30.10 & 7201.61 \\ coord200-10-2b.dat & 260,206.20 & 410,000.40 & 57.57 & 7202.89 \\ coord200-10-3.dat & 226,295.97 & 469,606.39 & 107.52 & 7201.38 \\ coord200-10-3b.dat & 225,896.31 & 497,752.47 & 120.35 & 7210.48 \\ coord35 pelle21-5.dat & 318.06 & 318.06 & 0.00 & 2.85 \\ coordGaspelle22-5.dat & 447.09 & 447.09 & 0.00 & 2.62 \\ coordGaspelle29-5.dat & 374.23 & 374.23 & 0.00 & 41.69 \\ coordGaspelle32-5.dat & 359.10 & 359.10 & 0.00 & 118.17 \\ coordGaspelle32-5b.dat & 383.41 & 383.41 & 0.00 & 529.44 \\ coordGaspelle36-5.dat & 399.37 & 399.37 & 0.00 & 14.89 \\ \hline Average & & & & 11.21 & 5221.63 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Exact method’s results. The results for the BRKGA with a local search are presented in Table 3. The algorithm was run using one and sixteen CPU cores, and the average running times are shown in columns _T1_ and _T16_, respectively. A predefined group of seeds was used for each of the five times the BRKGA was executed. Therefore, the result with one or sixteen CPU cores was identical for the same seed. The results show that using multiple threads significantly reduced the average elapsed time to solve the CLTPI instances. On average, using sixteen CPU cores was 8.10 times faster than using one CPU core. The best reduction in the running time achieved was 19.38, for instance, by \"coord200-10-2b.dat\", where the BRKGA was 13.73 times faster when using sixteen CPU cores instead of one CPU core. The maximum average running time using 16 CPU cores was 19.38, for instance, with \"coord200-10-2b.dat\".