## 3 Computational Results  
In this study, we performed substantial computational experiments to evaluate the proposed strategies for problem size, density, and \(r\)-value. We compared the performance of Algorithms 3-5 for \(r=2\) on very-large-scale QUBO instances. We also compared the best algorithm among Algorithms 3-5 to one of the best algorithms for \(x^{T}Qx\), i.e., [PERSON]'s multiple start tabu search. We coded the algorithms in C++ programming language. In [28], there are five multiple start tabu search algorithms, and the MST2 algorithm had the best results reported by the author. We chose the MST2 algorithm with the default values for the parameters recommended by the author [28]. In the MST2 algorithm, the number of iterations as the stopping criterion for the first tabu search start subroutine is 25,000\(\times\) the size of the problem, and then the MST2 algorithm reduces the number of iterations to 10,000\(\times\) the size of problem as the stopping criterion for the subsequent tabu search starts. Within the tabu search subroutine, if an improved solution is found, then the MST2 algorithm invokes a local search immediately. The CPU time limit in the MST2 algorithm is checked at the end of the tabu search start subroutine. Thus, the computing time might exceed the CPU time limit for large instances when choosing short CPU time limits. All algorithms in this study were compiled by GNU C++ compiler v4.8.5 and run on a single core of Intel Xeon Quad-core E5420 Harpertown processors, which have a 2.5 GHz CPU with an 8 GB memory. All computing jobs were submitted through the Open PBS Job Management System (Version 3) to ensure that both methods used the same CPU for memory usage and CPU time limits in the same instance. Preliminary results indicate that Algorithms 3-5 performed well in instances with a size of less than 3000 and low density. All algorithms found the best-known solution with a CPU time limit of 10 s. Thus, we only compared the results of large instances with high density and a size of 3000 to 8000 with the MST2 algorithm and the best algorithm among Algorithms 3-5. These benchmark instances with sizes of 3000 to 8000 have been reported by other researchers [5; 12]. In addition, we generated some very-large-scale QUBO instances with a high density and size of 30,000 using the same parameters from the benchmark instances. We used a CPU time limit of 600 s and \(r=2\) for Algorithms 3-5 in the very-large-scale instances in Table 2. We adopted the following notation for the computational results:OFV: The value of the objective function for the best solution found by each algorithm;  
BFS: The best solution found among algorithms within the CPU time limit;  
TB [s]: Time for each algorithm to reach the best solution in seconds;  
AT [s]: Average computing time out of 10 runs to reach OFV;  
DT: % Deviation of computing time out of 10 runs to reach OFV. Table 2 shows the results of the comparison for Algorithms 3-5 on very-large-scale instances out of 10 runs. Algorithm 5 produced a better solution than Algorithms 3 and 4 with \(r=2\); thus, we used Algorithm 5 with \(r=1\) and \(r=2\) to compare to the MST2 algorithm. We imposed a CPU time limit of 60 s and 600 s per run, with 10 runs per instance on Algorithm 5 and the MST2 algorithm. We choose a tabu tenure value of 100 for 1-flip and 2-flip. In our implementation, we chose the CPU time limit as the stopping criterion and checked the CPU time limit before invoking the tabu search in Algorithm 5. Because the MST2 algorithm and Algorithm 5 are not single point-based search methods, the choice of the CPU time limit as the stopping criterion seemed to be a fair performance comparison method between the algorithms. Table 3 describes the size and density of each instance and the number of times out of 10 runs the OFV was reached as well as the solution deviation within the CPU time limit for the MST2 algorithm and Algorithm 5 with \(r=1\) and \(r=2\). The MST2 algorithm produced a stable performance and reached the same OFV frequently out of 10 runs.