## 4 Benchmarking
### Test on Max-Cut Problems  
The representation of the max-cut problem in the QUBO problem can be found in [9]. Instead of using the QUBO form, we used the common formula for max-cut. Given undirected graph \(G=(V,E)\), with node set \(V=\{v_{1},v_{2},...,v_{n}\}\) and non-negative weight \(w_{ij}=w_{ji}\) on edge \((i,j)\in E\), a partition of G into two disjoint node subsets \(S\) and \(S^{c}\), which maximized the cut value, was found. \[cut(S,S^{c})=\sum_{a\in S,\beta\
otin S}w_{a\beta}. \tag{13}\]  
This definition corresponds to the following forms:  
\[max\;cut(S,S^{c}) =\frac{1}{2}\sum_{i<j}w_{ij}(1-x_{i}x_{j}),\] (14) s.t. \[x_{i},x_{j}\in\{-1,1\}, \tag{15}\]  
or  
\[max\;cut(S,S^{c}) =\sum_{i<j}w_{ij}(x_{i}-x_{j})^{2}, \tag{16}\] \[s.t. \ x_{i},x_{j}\in\{0,1\}. \tag{17}\]  
The \(\pm 1\) encoding was used on this test. We applied the local search process reported elsewhere [15; 30] on both the VNS and B-VNS algorithms. The local search process was carried out as follows: with \(X\) as the current solution that corresponds to partition \((S,S^{c})\), a new partition was defined \((S^{\prime},S^{c^{\prime}})\). \[(S^{\prime},S^{c^{\prime}})= \begin{cases}(S\setminus\{i\},\ S^{c^{\prime}} \cup\{i\})&\text{if node}\,i\in S\\ (S\cup\{i\},\ S^{c^{\prime}}\setminus\{i\})&\text{if node}\,i\in S^{c}\end{cases}  \tag{18}\]  
For each node \(i\in V\), a function \(\delta\) associated with solution \(X\) was defined as  
\[\delta(i)=\sum_{j\in S}w_{ij}-\sum_{j\in S^{c}}w_{ij}. \tag{19}\]  
In order to improve the objective value, a node \(i\) made a movement from a subset of \(V\) to another subset, regarding these situations: \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \(n\) & **Problem** & **Best** & & **VNS** & & & **B-VNS** & & **Test (\(p\)-Value) * \\  & **Number** & **Known** & **BestDif** & **AvDiff** & **Time** ** & **BestDif** & **AvDiff** & **Time** ** & **Dif** & **Time** \\ \hline
250 & 1 & 45,607 & 0 & 8 & 11.873 & 0 & 10.133 & 10.890 & 0.458 & *** \\  & 2 & 44,810 & 0 & 59.267 & 12.123 & 0 & 45.033 & 11.429 & 0.147 & 0.005 \\  & 3 & 49,037 & 0 & 0 & 8.996 & 0 & 0 & 8.662 & - & 0.045 \\  & 4 & 41,274 & 0 & 20.6 & 10.539 & 0 & 33.133 & 9.743 & 0.067 & *** \\  & 5 & 47,961 & 0 & 15.933 & 9.672 & 0 & 10.933 & 8.808 & 0.611 & *** \\  & 6 & 41,014 & 0 & 8.6 & 11.766 & 0 & 11.5 & 10.973 & 0.876 & *** \\  & 7 & 46,757 & 0 & 0 & 10.624 & 0 & 0 & 10.191 & & 0.050 \\  & 8 & 35,726 & 52 & 214.200 & 13.311 & 0 & 177 & 12.196 & 0.297 & *** \\  & 9 & 48,916 & 0 & 23.100 & 11.330 & 0 & 27.233 & 10.341 & 0.433 & *** \\  & 10 & 40,442 & 0 & 3.533 & 12.526 & 0 & 2.2 & 11.211 & 0.688 & *** \\ \hline
500 & 1 & 116,586 & 0 & 5.333 & 586.406 & 0 & 6.267 & 592.798 & 0.677 & 0.398 \\  & 2 & 128,339 & 0 & 2.5 & 459.926 & 0 & 4.4 & 455.013 & 0.402 & 0.374 \\  & 3 & 130,812 & 0 & 0 & 501.773 & 0 & 0 & 496.806 & - & 0.432 \\  & 4 & 130,097 & 0 & 28.933 & 518.133 & 0 & 26.733 & 523.351 & 0.486 & 0.321 \\  & 5 & 125,487 & 0 & 10.4 & 521.381 & 0 & 2.6 & 516.252 & 0.380 & 0.300 \\ \hline \hline \end{tabular}  
*: Mann–Whitney test, the difference is significant if \(p\)-value < \(a\), (\(a=0.05\)). **: average computation time (second). ***: -c0.001.  
\end{table} 
Table 2: _Cont._1. if \(i\in S\wedge\delta(i)>0\), then \(S=S\setminus\{i\},\ S^{\epsilon^{\prime}}=S^{\epsilon^{\prime}}\cup\{i\}\);
2. if \(i\in S^{\epsilon^{\prime}}\wedge\delta(i)<0\), then \(S^{\epsilon^{\prime}}=S^{\epsilon^{\prime}}\setminus\{i\},\ S=S\cup\{i\}\). This local search examined all of the possible movements starting from the first node. For [PERSON] et al. problems, parameter \(k_{max}\) was set at \(0.1n\), while \(p_{max}\) was set at \(0.1n\). The number of iterations was set at \(0.5n\), for both the VNS and B-VNS algorithms. We designed different test conditions for Helmberg-Rendl problems. Parameter \(k_{max}\) in the VNS algorithm was set at \(100\), for all of the Helmberg-Rendl problems used in the test, regardless of problem size, as suggested in [34].