## 2 New Results on Closed-Form Formulas
### Strategy 2  
Another efficient and easily implementable strategy is when, instead of using Equation (20), we only use an individual element to create a set of candidates for applying an \(r\)-flip search, set \(D(1)\), as defined below. Corollary 1 is a special case of Proposition 1 that suffices for such a strategy. \[D(1)=\{x_{i}:\left|E(x_{i})\right|<M\} \tag{24}\]  
**Corollary 1**. : _Let \(\varphi\) and \(M\) be as defined before. Given a solution \(x=(x_{1},\cdots,x_{n})\) of \(x^{T}Qx\), if the 1-flip local search cannot further improve the value of \(f(x)\), and \(i\in S\) with \(S\subseteq N\), where an \(r\)-flip move of elements of \(S\) improves \(f(x)\), then we must have \(\left|E(x_{i})\right|<M\)._  
To gain insight into the use of Corollary 1, we carried out some experimentation to find the size of set \(D(1)\) for different sizes of instances. The steps of the experiment to find the size of \(D(1)\) are provided below. The problems considered were taken from Ref. [26] and have been used by many researchers. We only used the larger-scale problems with 2500 to 6000 variables for a total of 38 instances. ```
Initialize: \(n\), \(x\), evaluate \(E(x)\), value of \(r\), \(M\) Flag = 1 1  Do while (Flag = 1) 2  Flag = 0 3  Call 1-flip local search: Algorithm 1 4  Sort variables according to \(\left|E\left(x_{\pi(i)}\right)\right|\leq\left|E\left(x_{\pi(i+1)}\right)\right|\), using Inequality (20) evaluate value of \(K\) 5  For \(j=\pi(1),\cdots,\pi(K):\) 6  For \(S_{j}=\left\{\pi(1),\cdots,\pi(j)\right\}\), evaluate \(M_{S_{j}}\)  If \(\sum_{i=1}^{j}\left|E\left(x_{\pi(i)}\right)\right|<M_{S_{j}}\), evaluate \(M\) using Equation (7). 7  If \(\Delta f>0\): \(x_{i}=1-x_{i}\), for \(i\in S_{j}\), update \(E(x)\) using Equation (8), Flag = 1, go to Step 1 8  End for  End while
```
**Algorithm 3**\(r\)-flip local search: strategy 1
```
Initialize: \(n\), \(x\), evaluate \(E(x)\), value of \(r\), \(M\) Flag = 1 1  Do while (Flag = 1) 2  Flag = 0, and \(S=\varnothing\) 3  Call 1-flip local search: Algorithm 1 4  Randomly choose a sequence \(\pi(1),\cdots,\pi(n)\) of integers \(1,\cdots,n\) 5  For \(j=\pi(1),\cdots,\pi(n)\): 6  If \(\left|E\left(x_{j}\right)\right|<M\), and \(\left|S\cup\left\{j\right\}\right|\leq r\) evaluate \(\Delta f\) for \(S\cup\left\{j\right\}\) using Equation (7) 7  If \(\Delta f>0\): \(x_{i}=1-x_{i}\), for \(i\in S\cup\left\{j\right\}\), update \(E(x)\) using Equation (8), \(S=S\cup\left\{j\right\}\), Flag =1, go to Step 1 8  End for  End while
```  
**Algorithm 4**\(r\)-flip local search: strategy 2  
In the Destruction() procedure, there are three steps:  
* Step 3a. Find the variable that is not on the tabu list and lead to the small change to the solution when the variable is flipped. * Step 3b. Change its value, place it on the tabu list to update the tabu list, and update \(E(x)\). * Step 3c. Test whether there is any variable that is not on the tabu list and that can improve the solution. If not, go to Step 3a. In the Construction() procedure, there are four steps:
* Step 4a. Test all of the variables that are not on the tabu list. If a solution better than the current best solution is found, change its value, place it on the tabu list, update \(E(x)\), update the tabu list, and go to Step 1. * Step 4b. Find the index \(i\) corresponding to the greatest value of \(E(x_{i})\), change its value of \(x_{i}\), place it on the tabu list to update the tabu list, and update \(E(x)\). * Step 4c. If this is the 15 th iteration in the Construction() procedure, go to Step 1. Step 4d. Test whether there is any variable that is not on the tabu list and that can improve the solution. If not, go to Step 3a. If yes, go to Step 4a. The randChange() procedure is invoked occasionally and randomly to select an \(x\) for the Destruction() using a random number generator. There is a probability of less than 2% of invoking after the Construction() procedure. To get the 2% probability, a random number generator is used to create an integer between 1 and 1000.