## 2 VNS Algorithm  
The VNS algorithm is a well-known metaheuristic algorithm that utilizes dynamic neighborhood structure changes. The simple implementation of the VNS algorithm starts from a non-deterministic _guest_ initial point and, then, attempts refinements using a local search. The algorithm shifts from its initial point to a neighboring point, before a local search is carried out. The algorithm should move to another neighborhood structure, when the local search does not yield a better solution. The algorithm systematically exploits the following observations [33]:  
_Observation 1_: A local minimum for one neighborhood structure is not necessarily so for another;  
_Observation 2_: A global minimum is a local minimum for all of the possible neighborhood structures;  
_Observation 3_: For many problems, local minimums for one or several neighborhoods are relatively similar to each other.  
In other words, according to observation 1, a local minimum for a specific neighborhood structure is not necessarily a local minimum for other neighborhood structures. Other neighborhoods may have other local optimums. The second observation means that the global minimum will only be found after examining all of the possible local optimums, which requires the examination of all of the possible neighborhood structures. Other neighborhoods should be examined, if a local minimum is not the global minimum. The last observation is an empirical observation that suggests a local optimum, usually, provides information that helps determine the global optimum [33]. For example, in the case of a multi-variable function, several variables, often, have the same value in the local optimum as in the global optimum [33].  
There are several versions of the VNS algorithm; the most prominent is the dynamic neighborhood model, proposed by [PERSON] and [PERSON] [14]. They proposed a random shift to a neighboring point \(\mathbf{X}^{\prime}\), which would be used instead of the initial point \(\mathbf{X}\), as the base point of a local search. They called this shifting \"shaking\". In this model, if the local search does not yield an improvement, the neighborhood structure is expanded. This change enables the algorithm to move to another basin to be exploited. To retain efficiency, the change must be limited by a parameter that defines the maximum number of neighborhood structures examined. If the local search yields an improvement, the structure is, suddenly, shrunk back to the first structure. The use of this clever expand-and-shrink neighborhood structure, during a search, enables the VNS algorithm to avoid the local optimum trap [30] because the algorithm moves from one basin to another. Figure 1a shows the searching process [32] in the context of minimization. The pseudocode of the VNS algorithm is shown in Figure 1b.  
A change in neighborhood structure can be illustrated as an expanded disc, with point \(\mathbf{X}\) at the center. The neighborhood structure expands, following variable \(k\in\mathbb{N}\). As proposed elsewhere [17; 31; 34], neighborhood structure \(N\) is associated with variable \(k\), which is limited by parameter \(k_{max}\in\mathbb{N}\). Thus, Hamming distance \(d\) increases, following \(k\), when solving QUBO problems. Accordingly, a point \(\mathbf{X}^{\prime}\in N_{k}(\mathbf{X})\) means that the Hamming distance \(d(\mathbf{X}^{\prime},\mathbf{X})=|\mathbf{X}^{\prime}-\mathbf{X}|\) is exactly \(k\). This neighborhood structure is the standard that is used in solving QUBO problems. The neighborhood structure of the basic VNS algorithm for use in solving QUBO problems is formulated as  
\[N_{k}(\mathbf{X})=\{\mathbf{Y}:\ |\mathbf{Y}-\mathbf{X}|=k\}, \tag{2}\]  
for \(k=1,2,...,k_{max}\).