## 1 Introduction  
Quadratic unconstrained binary optimization is a classic NP-hard problem that has been used as a unifying approach to many combinatorial optimization problems [1, 2]. Due to its practicality, as well as theoretical interest, over the years researchers have proposed many theoretical results as well as simple and sophisticated approaches as solution procedures [3, 4, 5, 6, 7, 8, 9, 10]. However, due to the complexity and practicality of QUBO, it is still necessary to provide results suitable for solving large-scale problems. In recent years, researchers have developed theoretical results to reduce the algorithmic implementation difficulty of QUBO, [11, 12, 13, 14, 15, 16]. Our results in this paper also help to reduce the size and difficulty of the algorithmic implementation of these problems. Quadratic unconstrained binary optimization (QUBO) can be formulated as:  
\[Max\ f(x)=\sum_{i=1}^{n}q_{i}x_{i}+\frac{1}{2}\sum_{i=1}^{n}\sum_{j\
eq i}^{n} q_{i,j}x_{i}x_{j},\ s.t.x_{i}\in\{0,1\},i=1,\cdots,n \tag{1}\]  
In Equation (1), \(\frac{1}{2}q_{i,j}\) is the \(ij\)-th entry of a given \(n\) by \(n\) symmetric matrix \(Q\). QUBO is often referred to as the \(x^{T}Qx\) model [17]. Since \({x_{i}}^{2}=x_{i}\)\(for\)\(x_{i}=0,1\), and \(Q\) may be written as an upper triangular matrix by doubling each entry of the upper triangle part of the matrix and letting \(q_{i,i}=q_{i}\), then we can write Equation (1) as Equation (2). \[Max\ f(x)=\sum_{i=1}^{n}\sum_{j\geq i}^{n}q_{i,j}x_{i}x_{j}=x^{T}Qx,\ s.t.x_{ }j\in\{0,1\},i=1,\cdots,n \tag{2}\]  
Local search strategy (LSS) is one of the most fundamental algorithmic concepts and has been successfully applied to a wide range of hard combinatorial optimization problems. The basic ingredient of almost all sophisticated heuristics is some variation of LSS. One LSS that has been used by many researchers as a stand-alone or as a basic component of more sophisticated algorithms is the \(r\)-flip (also known as \(r\)-Opt) strategy [11; 18; 19; 20; 21; 22]. In Table 11, we present a comprehensive review of \(r\)-flip strategies applied to QUBO. Let \(N=\{1,2,\,\ldots,n\}\). Given a binary solution, \(x=(x_{1},\cdots,x_{n})\) of \(x^{T}Qx\), the \(r\)-flip search chooses a subset, \(S\subseteq N\), with \(|S|\leq r\), and builds a new solution, \(x^{\prime}\), where \(x^{\prime}_{i}=1-x_{i}\) for all \(i\in S\). If \(x^{\prime}\) improves the objective function, it is called an improving move (or improving subset \(S\)). The \(r\)-flip search starts with a solution \(x\), chooses an improving subset \(S\), and flips all elements in \(S\). The process continues until there is no subset \(S\) with \(|S|\leq r\) that improves the objective function. The result is called a locally optimal solution with respect to the \(r\)-flip move (or \(r\)-Opt). Often in strategies where variable neighborhood searches, such as fan-and-filter (F&F) [23; 24], variable neighborhood search (VNS) [25; 26], and multi-exchange neighborhood search (MENS) [18; 19; 20; 21; 22] are used, the value of \(r\) dynamically changes as the search progresses. Generally, there are two reasons for a dynamically changing search space strategy. 1. The execution of an implementation of an \(r\)-flip local search, for a larger value of \(r\), can be computationally expensive to execute. This is because the size of the search space is of order \(n\) chosen \(r\), and for fixed values of \(n\), it grows quickly in \(r\) for the value of \(r\leq\lfloor n/2\rfloor\). Hence, smaller values of \(r\), especially \(r\) equal to 1 and 2, have shown considerable success. 2. In practice, an \(r\)-flip local search process with a small value of \(r\) (e.g., \(r=1\)) can quickly reach local optimality. Thus, as a way to escape 1-flip local optimality, researchers have tried to dynamically change the value of \(r\) as the search progressed. This offers an opportunity to expand the search to a more diverse solution space.