# Finding the Best 3-OPT Move in Subcubic Time
## 4 Searching the 3-OPT Neighborhood
### Implementing the Search Procedure  
We now describe more formally the procedure that finds the best improving 3-OPT move. To simplify the description of the code, we will make use of a global variable \(\mu^{*}\) representing the current champion move. Initially \(\mu^{*}\) is NULL, and we extend the function \(\Delta()\) by defining \(\Delta(\texttt{NULL}):=0\). The main procedure is Find3-OPTmove (Procedures 1 and 2). The procedure starts by setting \(\mu^{*}\) to a solution for which, possibly, \(\Delta(\mu^{*})>0\). This is not strictly necessary, and setting \(\mu^{*}\) to NULL would work too, but a little effort in finding a \"good\" starting champion can yield a smaller heap and thus a faster, overall, procedure. In our case, we have chosen to just sample \(4n\) random solutions and keep the best. ```
1\(\mu^{*}\leftarrow\texttt{startingSolution}()\)
2\(H\leftarrow\texttt{buildHeap}()\)
3 while\(\big{(}H[1].\texttt{val}>\Delta(\mu^{*})/3\big{)}\)
4\((x,y,\alpha,r)\leftarrow\texttt{extractMax}(H)\)
5 for\(z\in\texttt{range3 rd}(x,y,\alpha)\)
6\((i,j,k)\leftarrow\texttt{selection}(x,y,z,\alpha)\)
7 if\((\Delta((i,j,k),r)>\Delta(\mu^{*}))\)then/*update global optimum */
8\(\mu^{*}\leftarrow((i,j,k),r)\)
9\(/*\) if\(\mu^{*}=\texttt{NULL}\) there are no improving moves */
```  
**Procedure 2** StartingSolution ()  
**Output:** move \(\mu\) (such that \(\Delta(\mu)\geq 0\))  
The procedure then builds a max-heap (see Procedure 3 BuildHeap) containing an entry for each \(r\in r_{1},\ldots,r_{4}\), \(\alpha\in\{12,23,13\}\) and \((x,y)\in\mathcal{S}_{\alpha}\) such that \(f_{r}^{\alpha}(x,y)>\Delta(\mu^{*})/3\). The specific functions \(f_{r}^{\alpha}\), for each \(\alpha\) and \(r\), are detailed in Table 2 of Section 6. The heap is implemented by an array \(H\) of records with five fields: \(x\) and \(y\), which represent two indices of a selection; alpha which is a label identifying the two type of indices; val which is the numerical value used as the key to sort the heap; and scheme which is a label identifying a reinsertion scheme. By using the standard implementation of a heap (see, e.g., [15]), the array corresponds to a complete binary tree whose nodes are stored in consecutive entries from \(1\) to \(H.\texttt{SIZE}\). The left son of node \(H[t]\) is \(H[2t]\), while the right son is \(H[2t+1]\). The father of node \(H[t]\) is \(H[t.\texttt{div.2}]\). The heap is such that the key of each node \(H[t]\) is the largest among all the keys of the subtree rooted at \(H[t]\). In the procedure BuildHeap we use a function \(\texttt{rangelst2 nd}(\alpha)\) which returns the set of all values that a pair \((x,y)\) of indices of type \(\alpha\) can assume. More specifically,  
* range1 st2 nd\((12):=\{(x,y):0\leq x<x+2\leq y\leq\bar{n}-2-\mathcal{P}(x=0)\}\) /* \(x\) is \(i_{1}\) and \(y\) is \(i_{2}\) */
* range1 st2 nd\((23):=\{(x,y):2+\mathcal{P}(y=\bar{n})\leq x<x+2\leq y\leq\bar{n}\}\) /* \(x\) is \(i_{2}\) and \(y\) is \(i_{3}\) */
* range1 st2 nd\((13):=\{(x,y):0\leq x<x+4\leq y\leq\bar{n}-\mathcal{P}(x=0)\}\) /* \(x\) is \(i_{1}\) and \(y\) is \(i_{3}\)BuildHeap terminates with a set of calls to the procedure Heapify (a standard procedure for implementing heaps), described in Procedure 4. To simplify the code, we assume \(H[t].\texttt{val}\) to be defined also for \(t>H.\texttt{SIZE}\), with value \(-\infty\). The procedure Heapify\((H,t)\) requires that the subtree rooted at \(t\) respects the heap structure at all nodes, except, perhaps, at the root. The procedure then adjusts the keys so that the subtree rooted at \(t\) becomes indeed a heap. The cost of heapify is linear in the height of the subtree. The loop of line 14 in procedure BuildHeap turns the unsorted array \(H\) into a heap, working its way bottom-up, in time \(O(H.\texttt{SIZE})\).