## 4 Benchmarking  
Considering that the B-VNS algorithm is a modification of the basic VNS algorithm, it is fair and appropriate to investigate the performance of our proposed B-VNS algorithm, alongside the VNS algorithm [17; 30] alone. The investigation did not involve any other algorithms. Therefore, the impact of our modification can be evaluated, by using VNS algorithm performances as the bases.  
The investigation was conducted by running simulations on some standard QUBO problems. The QUBO problems were taken from OR-Library [35] available at [36]. The best-known objective functions for those problems were compiled from [10; 11; 37; 38; 12]. We, also, tested the B-VNS algorithm, to solve some standard max-cut problems. We used problems from Helmberg-Rendl [39] that can be downloaded from [40]. Those problems were generated using a machine-independent graph generator, called rudy, which [PERSON] developed. We, also, tested the B-VNS algorithm on problems proposed by [PERSON], [PERSON], and [PERSON] [41], as they have different problem constructions. Helmberg-Rendl problems consist of random, planar, and toroidal graphs, while those from [PERSON] et al. are cubic lattice graphs that represent Ising spin-glass models [34].  
Figure 3: Neighborhood structure. (**a**) The neighborhood structure of B-VNS becomes wider according to probability \(p_{c}\), while (**b**) the neighborhood structure of basic VNS becomes wider according to variable \(k=1,2,...,k_{max}\)[32].  
Figure 2: Distribution of \(\mathbf{X}^{\prime}\) related to \(p\). A neighboring point \(\mathbf{X}^{\prime}\) having distance \(npc\) has a high probability of appearing.  
Problems by [PERSON] et al. can be downloaded from [42]. The best-known max-cut values were summarized from [34; 43; 44; 45; 46]. It is worth noting that all of those best-known values for QUBO and max-cut problems are open for improvement and may change in the future.  
The simulation program used, practically, the same program code written in Fortran for both the VNS and B-VNS algorithms. The only difference was in the neighborhood construction section, where the remaining sections were the same. Therefore, we could accurately measure the performance difference between our proposed neighborhood structure and the standard VNS algorithm structure.  
The simulation was compiled and run on a CentOS 8 system, powered by an Intel Core i7-8700 processor with 16 GB RAM. The simulation was, independently, run 30 times for each problem (\(NSim=30\)). Therefore, the sample size for both the VNS and B-VNS algorithms on each test item was 30, which was sufficient for the conduction of statistical tests. The best objective value and computation time, obtained for each iteration and simulation, were recorded. We used three criteria to evaluate the performance. After obtaining the best-known values, we calculated the difference (\(BestDif\)) between the best-known value and the best value, obtained from 30 simulations. If \(BestDif=0\), then the algorithm obtained the best-known value. A value of \(BestDif>0\) means the algorithm failed to obtained the best-known value. On the other hand, \(BestDif<0\) means the algorithm exceeded the best-known value.  
\[BestSim=max(\{f_{Sim_{i}}:i=1,2,...,NSim\}), \tag{10}\]  
\[BestDif=BestKnown-BestSim. \tag{11}\]  
We calculated the average differences (\(AvgDiff\)) between the best-known and obtained objective values, involving all 30 simulations.  
\[AvgDiff=\frac{\sum_{i=1}^{NSim}(f_{Sim_{i}}-BestKnown)}{NSim}. \tag{12}\]  
Lastly, we calculated the average computation time (\(AvgT\)). Regarding all of the criteria, the algorithm that gives the lowest results is the best one. However, as the direct comparison of samples by their average values may have led to a biased conclusion, we conducted statistical analysis to precisely compare the results, using JASP [47].