# Finding the Best 3-OPT Move in Subcubic Time
## 4 Searching the 3-OPT Neighborhood
### Implementing the Search Procedure
```
1.\(ls\gets 2t\) /* left son */
2.\(rs\gets 2t+1\) /* right son */
3.if\(\big{(}H[ls].\texttt{val}>H[t].\texttt{val}\big{)}\)then\(large\gets ls\)else\(large\gets t\)
4.if\(\big{(}H[rs].\texttt{val}>H[large].\texttt{val}\big{)}\)then\(large\gets rs\)
5.if\(\big{(}large\
eq t\big{)}\)then
6.\(H[t]\leftrightarrow H[large]\) /* swaps\(H[t]\) with the largest of its sons */
7.\(\texttt{heapify}(H,large)\)
```  
**Procedure 4**Heapify\((H,t)\)  
**Input:** array \(H\), integer \(t\in\{1,\ldots H.\texttt{SIZE}\}\)  
Coming back to Find3-OPTMove, once the heap has been built, a loop (lines 3-8) extracts the partial moves from the heap, from the most to the least promising, according to their value (field val). For each partial move popped from the heap we use a function \(\texttt{range3 rd}(x,y,\alpha)\) to obtain the set of all values for the missing index with respect to a pair \((x,y)\) of type \(\alpha\). More specifically. * range3 rd\((x,y,12):=\{z:y+2\leq z\leq\bar{n}-\mathcal{P}(x=0)\}\) /* missing index is \(i_{3}\) */
* range3 rd\((x,y,23):=\{z:0+\mathcal{P}(y=\bar{n})\leq z\leq x-2\}\) /* missing index is \(i_{1}\) */
* range3 rd\((x,y,13):=\{z:x+2\leq z\leq y-2\}\) /* missing index is \(i_{2}\) */ ```
We then complete the partial move in all possible ways, and each way is compared to the champion to see if there has been an improvement (line 7). Whenever the champion changes, the condition for loop termination becomes easier to satisfy than before. In line 6 we use a function selection\((x,y,z,\alpha)\) that, given three indices \(x\), \(y\), \(z\) and a pair type \(\alpha\), rearranges the indices so as to return a correct selection. In particular, selection\((x,y,z,12):=(x,y,z)\), selection\((x,y,z,23):=(z,x,y)\), and selection\((x,y,z,13):=(x,z,y)\). The procedure ExtractMax (in the Procedure 5) returns the element of a maximum value of the heap (which must be in the root node, i.e., \(H[1]\)). It then replaces the root with the leaf \(H[H.SIZE]\) and, by calling heapify\((H,1)\), it moves it down along the tree until the heap property is again fulfilled. The cost of this procedure is \(O(\log(H.SIZE))\). ```
Input: heap \(H\) Output: the partial move \((x,y,\alpha,r)\) of maximum value in \(H\)
```
**Procedure 5** ExtractMax (\(H\))  
**Input:** heap \(H\)  
**Output:** the partial move \((x,y,\alpha,r)\) of maximum value in \(H\)  
1. \((x,y,\alpha,r)\leftarrow(H[1].x,H[1].y,H[1].\texttt{alpha},H[1].\texttt{scheme})\) /* gets the max element */
2. \(H[1]\gets H[H.SIZE]\) /* overwrites it */
3. \(H.SIZE\gets H.SIZE-1\)
4. heapify\((H,1)\) /* restores the heap */
5. return\((x,y,\alpha,r)\)
```

**Algorithm 5** ExtractMax (\(H\))

## 5 Computational Results

In this section, we report on our extensive computational experiments showing the effectiveness of the approach we propose. All tests were run on a Intel(r)CoreTM i7-7700 8 CPU under Linux Ubuntu, equipped with 16 GB RAM at 3.6 GHz clock. The programs were implemented in C, compiled under gcc 5.4.0 and are available upon request,

### Instance Types

The experiments were run on two types of graphs: (i) random graphs generated by us and (ii) instances from the standard benchmark repository TSPLIB [16]. The random graphs are divided into three categories:

* Uniform (UNI): complete graphs in which the edge costs are independent random variables drawn uniformly in the range \([0,1]\). * Gaussian (GAU): complete graphs in which the edge costs are independent random variables drawn according to the Gaussian distribution \(N(\mu,\sigma)\) with mean \(\mu=0.5\) and standard deviation \(\sigma=0.1\). * Geometric (GEO): complete graphs in which the edge costs are the Euclidean distances between \(n\) random points of the plane. In particular, the points are generated within a circle of radius 1 by drawing, u.a.r. a pair of polar coordinates \((d,\alpha)\), where \(d\in[0,1]\) and \(\alpha\in[0,2\pi]\).