## 4 Computational Experimentation
### Application of the Multi-BB Parallel Algorithm
#### 4.2.1 Solution of the Weakly Correlated Instance of Series 6 (with \(n=800\))  
The first application of the multi-BB algorithm was to solve the weakly correlated instance of series 6 (with \(n=800\)), which required 47,107.17 s. To measure the results of the parallel implementation, speedup and parallel efficiency were used, which are described in Equations (17) and (18):  
\[Speedup:\ Sp=\ \frac{Sequential\ runtime}{Runtime\ in\ processors}, \tag{17}\]  
\[Parallel\ efficiency:\ Ep=\frac{Speedup\ with\ p\ processors}{number\ of\ processors\ p}. \tag{18}\]  
The ideal speedup value is a linear value, that is, \(S_{p}=p\) (number of processors). However, for parallel efficiency, its ideal value is equal to 1 or 100%. Table 8 shows the execution time, the speedup \(\left(S_{p}\right)\), and the parallel efficiency \(\left(E_{p}\right)\) for different numbers of cores.  
As is shown in Table 8, the weakly correlated instance of series 6 (with \(n=800\)) could be solved in parallel with different numbers of cores. Because binary trees are generated to explore different solution spaces, by fixing and removing elements, it is possible to reduce parallel computation times. This is due to the calculation of optimal local solutions, which allow for more efficient calculations of the global optimal solution. This method is used in all binary trees to determine which branches are pruned or branched. The multi-BB algorithm accelerates its calculation process by sending the global optimal solution to each interval of the local iterations, allowing for the pruning of a greater number of branches of each binary tree. In this case, the elements selected to be fixed or removed were correct because the parallel execution time was reduced: only on two occasions was a superlinear speedup achieved. This scenario could change if another method for selecting the numbers of elements to be  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Machine–Cores** & **20** & **40** & **60** & **80** & **100** & **120** \\ \hline  & 5 & 10 & 15 & 25 & 30 & 30 \\  & 5 & 10 & 15 & 25 & 40 & 60 \\  & 5 & 10 & 15 & 15 & 15 & 15 \\  & 5 & 10 & 15 & 15 & 15 & 15 \\  & 5 & 10 & 15 & 15 & 15 & 15 \\ \hline \hlinefixed or removed in the decision trees is used. The two times a superlinear speedup was reached were when 20 and 80 processing units were used. Parallelism in these algorithms is speculative because dependencies are ignored and subtrees are explored in a parallel form whose algorithm efficiencies can result in an anomalous performance, as defined in Reference [29]: \"It may be that a parallel task finds a strong incumbent more quickly than in the sequential execution, leading to less work being done. In this case we observe superlinear speedups.\" In the first case of a speedup, 144.87 was reached, which was much higher than the 20 cores used. In the second case, a speedup of 86.14 with 80 cores was achieved. These two cases gave parallel efficiencies of 724.36% and 107.67%, on speedup respectively, which were both higher than the ideal value of 100%. In the other solved cases, a superlinear speedup was not reached, and the efficiencies were lower than 100%. Figure 6 shows the workload when 20 processing units were used.  
As is seen in Figure 7, 4 of the 20 processing units concluded their calculations in the first iterations, and a fifth processor concluded its calculations as 20% of the iterations converged. Thus, the Ioevolution cluster required approximately 75% efficiency to obtain an optimal solution. The above results indicate that the execution time was algorithmically reduced, but not by the efficient use of the Ioevolution cluster. This indicates that the hypothesis of reducing the number of operations is possibly true if the operation starts from another point in the search space of feasible solutions.