# Finding the Best 3-OPT Move in Subcubic Time
## 4 Searching the 3-OPT Neighborhood
With respect to the strategy outlined in Section 3, this corresponds to a criterion for deciding if a partial move suggested by our heuristic box is worth expanding into all its completions. Assume we want to find the best move overall and the best move we have seen so far (the current \"champion\") is \(\mu^{*}\). We make the key observation that for a move \(((i_{1},i_{2},i_{3}),r)\) to beat \(\mu^{*}\) it must be  
\[\Delta((i_{1},i_{2},i_{3}),r).\]7  
These three conditions are not exclusive but possibly overlapping, and in our algorithm, we will enumerate only moves that satisfy at least one of them. Furthermore, we will not enumerate these moves with a complete enumeration, but rather from the most promising to the least promising, stopping as soon as we realize that no move has still the possibility of being the best overall. The most appropriate data structure for performing this kind of search (which hence be used for our heuristic implementation of the magic box described in Section 3) is the Max-Heap. A heap is perfect for taking the highest-valued elements from a set, in decreasing order. It can be built in linear time with respect to the number of its elements and has the property that the largest element can be extracted in logarithmic time, while still leaving a heap. We then build a max-heap \(H\) whose elements are records of type  
\[\Delta((i_{1},i_{2},i_{3}),r).\]8  
where \(\alpha\in\{12,13,23\}\), \(r\in\{r_{1},r_{2},r_{3},r_{4}\}\), \((x,y)\in\mathcal{S}_{\alpha}\), and \(f:=f_{r}^{\alpha}(x,y)\). The heap elements correspond to partial moves. The heap is organized according to the values of \(f\), and the field \(\alpha\) is a label identifying which selection indices are associated to a given heap entry. We initialize \(H\) by putting in it an element for each \((x,y)\), \(r\) and \(\alpha\) such that \(f_{r}^{\alpha}(x,y)>\Delta(\mu^{*})/3\). We then start to extract the elements from the heap. Let us denote by \([x^{j},y^{i},f^{j},\alpha^{i},r]\) the \(j\)-th element extracted. Heuristically, we might say that \(x^{1}\) and \(y^{1}\) are the most likely values that a given pair of indices (specified by \(\alpha^{1}\)) can take in the selection of a best-improving move, since these values give the largest possible contribution to the move value (2). We will keep extracting the maximum \([x^{j},y^{i},f^{j},\alpha^{i},r^{i}]\) from the heap as long as \(f^{j}>\Delta(\mu^{*})/3\). This does not mean that we will extract all the elements of \(H\), since \(\Delta(\mu^{*})\) could change (namely, increase) during the search and hence the extractions might terminate before the heap is empty. Each time we extract the heap maximum, we have that \(x^{j}\) and \(y^{j}\) are two possible indices out of three for a candidate move to beat \(\mu^{*}\). With a linear-time scan, we then enumerate the third missing index (identified by \(\alpha^{j}\)) and see if we get indeed a better move than \(\mu^{*}\). For example, if \(\alpha^{j}=13\) then the missing index is \(i_{2}\) and we run a for-loop over \(i_{2}\), with \(x^{j}+2\leq i_{2}\leq y^{j}-2\), checking each time if the move \(((x^{j},i_{2},y^{j}),r^{j})\) is a better move than \(\mu^{*}\). Whenever this is the case, we update \(\mu^{*}\). Note that,since \(\Delta(\mu^{*})\) increases, the number of elements still in the heap for which \(f>\Delta(\mu^{*})/3\) after updating the champion may be considerably smaller than it was before the update. When the procedure outlined above terminates, \(\mu^{*}\) is an optimal move. Suppose, by contradiction, that there exists a move \(\mu=((w_{1},w_{2},w_{3}),r)\) better than \(\mu^{*}\). Since \(\Delta((w_{1},w_{2},w_{3}),r)>\Delta(\mu^{*})\), there exists at least one pair \(a<b\in\{1,2,3\}\) such that \(f_{r}^{ab}(w_{a},w_{b})>\Delta(\mu^{*})/3\). Then the partial move \((w_{a},w_{b},f_{r}^{ab}(w_{a},w_{b}),ab,r)\) would have eventually been popped from the heap and evaluated, producing a move better than \(\mu^{*}\). Therefore the procedure could not have ended with the move \(\mu^{*}\).