## 1 Introduction
### Previous Works  
The development of closed-form formulas for \(r\)-flip moves is desirable for developing heuristics for solving very-large-scale problem instances because it can reduce computational time consumed by the implementation of an algorithm. [PERSON] and [PERSON] [11] introduced several theorems showing closed-form \(r\)-flip formulas for general pseudo-Boolean optimization. The authors in [12; 13] recently provided closed-form formulas for evaluating \(r\)-flip rules in QUBO. In particular, Theorem 6 in [11] is specific to the \(f(x)=x^{T}Qx\) problem. To explain the closed-form formula for the \(r\)-flip rule in \(x^{T}Qx\), we first introduce a few definitions. Refer to Table 11 for an exhaustive list of literature on \(r\)-flip rules applied to QUBO. Given a solution \(x=(x_{1},\cdots,x_{n})\), the derivative of \(f(x)\) with respect to \(x_{i}\) is defined as:  
\[E(x_{i})=q_{i}+\sum_{j<i}q_{j,i}x_{j}+\sum_{j>i}q_{i,j}x_{j},\ i=1,\cdots,n \tag{3}\]It is well known that any locally optimal solution to an instance of the QUBO problem with respect to a 1-flip search satisfies  
\[\mathit{Either}\ \left(\left(x_{i}=0\right)\ \mathit{iff}\ E(x_{i})<0\right) \ \mathit{or}\ \left(x_{i}=1\ \mathit{iff}\ E(x_{i})\geq 0\right),\ \mathit{for}\ i=1,\cdots,n \tag{5}\]  
Furthermore, after changing \(x\) to \(x^{\prime}\), the update for \(E\big{(}x_{j}\big{)},j=1,\ldots,n\), can be calculated as follows:  
\[ \begin{array}{l}\forall j<i,E\big{(}x_{j}\big{)}\gets E\big{(}x_{j} \big{)}+q_{j,i}\big{(}x_{i}^{\prime}-x_{i}\big{)}\\ \forall j>i,E\big{(}x_{j}\big{)}\gets E\big{(}x_{j}\big{)}+q_{i,j}\big{(}x _{i}^{\prime}-x_{i}\big{)}\\ =,\ \ E\big{(}x_{j}\big{)}\gets E\big{(}x_{j}\big{)}\ \ \ j=1,\ldots,n\end{array}  \tag{6}\]  
Note that \(x_{i}^{\prime}-x_{i}\) may be written as \(1-2x_{i}\), which can simplify the implementation process. A simple 1-flip search is provided in Algorithm 1. Note that in line 3 we chose a sequence to implement Fact 1. Using such a strategy has experimentally proven to be very effective in several recent studies [27]. Before we present the algorithms in this study for the \(r\)-flip strategy, the notations used are given as follows:  
\(n\): The number of variables;  
\(x\): A starting feasible solution;  
\(x^{\star}\): The best solution found so far by the algorithm;  
\(K\): The largest value of \(k\) for \(r\)-flip, \(k\leq r\);  
\(\Pi(i)\): The \(i\)-th element of \(x\) in the order \(\pi(1)\cdots\pi(n)\);  
\(S\): = \(\{i:x_{i}\}\) is tentatively chosen to receive a new value to produce a new solution \(x_{i}^{\prime}\)\(\}\) restricting consideration to \(|S|=r\);  
\(D\): The set of candidates for an improving move;  
Tabu_ten: The maximum number of iterations for which a variable can remain tabu;  
Tabu(\(i\)): A vector representing tabu status of \(x\);  
\(E(x_{i})\): Derivative of \(f(x)\) with respect to \(x_{i}\);  
\(E(x)=\left(E(x_{1}),\ldots,E(x_{n})\right)\) The vector of derivatives;  
\(X(. )\): A vector representing the solution of \(x\);  
\(E(. )\): A vector representing the value of derivative \(E(x_{i})\). ```
Initialize: \(n\), \(x\), evaluate the vector \(E(x)\) Flag = 1  Do while (Flag = 1)  Flag = 0  Randomly choose a sequence \(\pi(1),\ldots,\pi(n)\) of integers 1,\(\ldots\),\(n\). Do I = \(\pi(1),\ldots,\pi(n)\)  If \(\left(E(x_{i})<0\ \mathit{and}\ x_{i}=1\right)\ \mathit{or}\ \left(E(x_{i})>0\ \mathit{and}\ x_{i}=0\right)\): \(x_{i}=1-x_{i}\), update the vector \(E(x)\) using Equation (6), Flag = 1  End do  End do  End while
```  
**Algorithm 1**1-flip local search. The result of Fact 1 was extended to the \(r\)-flip search, given below. (Theorem 6, [PERSON] and [PERSON] [11]) Let \(x\) be a given solution of QUBO and \(x^{\prime}\) obtained from \(x\) by the \(r\)-flip move (for a chosen set \(S\)), where \(S\subseteq N,\ |\ S\mid=r\).