# Finding the Best 3-OPT Move in Subcubic Time
## 1 Introduction
### The K-OPT Neighborhood  
Let \(K\in\mathbb{N}\) be a constant. A \(K\)-OPT move on a tour \(T\) consists of first removing a set \(R\) of \(K\) edges and then inserting a set \(I\) of \(K\) edges so as \((T\setminus R)\cup I\) is still a tour (we include, possibly, \(R\cap I\
eq\emptyset\). This implies that the \((K-1)\)-OPT moves are a subset of the \(K\)-OPT moves). A \(K\)-OPT move is improving if \(c((T\setminus R)\cup I)<c(T)\) i.e., \(c(I)<c(R)\). An improving move is best improving if \(c(R)-c(I)\) is the maximum over all possible choices of \(R\), \(I\). The standard local search approach for the TSP based on the \(K\)-OPT neighborhood starts from any tour \(T^{0}\) (usually a random permutation of the vertices) and then proceeds along a sequence of tours \(T^{1},T^{2},\ldots,T^{N}\) where each tour \(T^{j}\) is obtained by applying an improving \(K\)-OPT move to \(T^{j-1}\). The final tour \(T^{N}\) is such that there are no improving \(K\)-OPT moves for it. The hope is that \(T^{N}\) is a good tour (optimistically, a global optimum) but its quality depends on many factors. One of them is the size of the neighborhood, the rationale being that with a larger-size neighborhood we sample a larger number of potential solutions, and hence increase the probability of ending up at a really good one. Clearly, there is a trade-off between the size of a neighborhood and the time required to explore it, so that most times people resort to the use of small neighborhoods since they are very fast to explore (for a discussion on how to deal with some very large size, i.e., exponential, neighborhoods for various combinatorial optimization problems, see [5]). The exploration of the \(K\)-OPT neighborhood, for a fixed \(K\), might be considered \"fast\" from a theoretical point of view, since there is an obvious polynomial algorithm (complete enumeration). However, in practice, complete enumeration makes the use of \(K\)-OPT impossible already for \(K=3\) (if \(n\) is large enough, like 3000 or more). There are \(\Theta(n^{K})\) choices of \(K\) edges to remove which implies that 3-OPT can be explored in time \(O(n^{3})\) by listing all possibilities. For a given tour \(n=6000\) nodes, the time required to try all 3-OPT moves, on a reasonably fast desktop computer, is more than one hour, let alone converging to a local optimum. For this reason, 3-OPT has never been really adopted for the heuristic solution of the TSP. The first use of \(K\)-OPT dates back to 1958 with the introduction of 2-OPT for the solution of the TSP in [6]. In 1965 [PERSON] [7] described the 3-OPT neighborhood, and experimented with the \(\Theta(n^{3})\) algorithm, on which he also introduced a heuristic step fixing some edges of the solution (at risk of being wrong) with the goal of decreasing the size of the instance. Still, the instances which could be tackled at the time were fairly small (\(n\leq 150\)). Later in 1968, [PERSON] and [PERSON] [8] described an improvement over [PERSON]'s method which made it 2 or 3 times faster, but still cubic in nature. It was soon realized that the case \(K\geq 3\) was impractical, and later local search heuristics deviated from the paradigm of complete exploration of the neighborhood, replacing it with some clever ways to heuristically move from tour to tour. The best such heuristic is probably [PERSON] and [PERSON]'s procedure [9] which applies a sequence of \(K\)-OPT moves for different values of \(K\). Notice that our objective, and our approach, is fundamentally different from [PERSON] and [PERSON]'s in that we always look for the best \(K\)-OPT move, and we keep \(K\) constantly equal to 3. On the other hand, [PERSON] and [PERSON], besides varying \(K\), apply a heuristic search for the best \(K\)-OPT move, which is fast but cannot guarantee to find the best move, and, indeed, is not guaranteed to find an improving move even if some exist. For a very good chapter comparing various heuristics for the TSP, including the 3-OPT neighborhood, see [PERSON] and [PERSON] [10].