# Finding the Best 3-OPT Move in Subcubic Time
## 1 Introduction  
The Traveling Salesman Problem (TSP), in all likelihood the most famous combinatorial optimization problem, calls for finding the shortest Hamiltonian cycle in a complete graph \(G=(V,E)\) of \(n\) nodes, weighted on the arcs. In this paper we consider the symmetric TSP, i.e., the graph is undirected and the distance between two nodes is the same irrespective of the direction in which we traverse an edge. Let us denote by \(c(i,j)=c(j,i)\) the distance between any two nodes \(i\) and \(j\). We call each solution of the problem a tour. A tour is identified by a permutation of vertices \((v_{1},\ldots,v_{n})\). We call \(\{v_{i},v_{i+1}\}\), for \(i=1,\ldots,n-1\), and \(\{v_{n},v_{1}\}\) the edges of the tour. The length of a tour \(T\), denoted by \(c(T)\) is the sum of the lengths of the edges of the tour. More generally, for any set \(F\) of edges, we denote by \(c(F)\) the value \(\sum_{c\in F}c(e)\).  
A large number of applications over the years have shown that local search is often a very effective way to tackle hard combinatorial optimization problems, including the TSP. The local search paradigm applies to a generic optimization problem in which we seek to minimize an objective function \(f(x)\) over a set \(X\). Given a map \(N:X\mapsto 2^{X}\) which associates to every solution \(x\in X\) a set \(N(x)\) called its neighborhood, the basic idea is the following: start at any solution \(x^{0}\), set \(s:=x^{0}\), and look for a solution \(x^{1}\in N(s)\) better than \(s\). If we find one, we replace \(s\) with \(x^{1}\) and iterate the same search. We continue this way until we get to a solution \(s\) such that \(f(s)=\min\{f(x)|x\in N(s)\}\). In this case, we say that \(s\) is a local optimum. Replacing \(x^{i}\) with \(x^{i+1}\) is called performing a move of the search, and \(N(s)\) is the set of all solutions reachable with a move from \(s\). The total number of moves performed to get from \(x^{0}\) to the final local optimum is called the length of the convergence. If \(x\) is a solution reachable with a move from \(s\) and \(f(x)<f(s)\) we say that the move is an improving move and \(x\) is an improving solution. When searching in the neighborhood of \(x^{i}\) we can adopt two main strategies, namely first-improvement and best-improvement (also called steepest-descent). In the first-improvement strategy, we set \(x^{i+1}\) to be the first solution that we find in \(N(x^{i})\) such that \(f(x^{i+1})<f(x^{i})\). In best-improvement, we set \(x^{i+1}\) to be such that \(f(x^{i+1})=\min\{f(x)|x\in N(x^{i})\wedge f(x)<f(x^{i})\}\). For small-size neighborhoods such asthe one considered in this paper, most local search procedures choose to adopt the best-improvement strategy, since it causes the largest decrease in the objective function value at any given iteration of the search. In this paper we will focus precisely on the objective of finding the best possible move for a popular TSP neighborhood, i.e., the 3-OPT.  
The idea of basic local search has been around for a very long time and it is difficult to attribute it to any particular author. Examples of its use are reported in standard textbooks on combinatorial optimization, such as [1], or devoted surveys, such as [2]. In time, many variants have been proposed to make local search more effective by avoiding it to get stuck in local optima. Namely, sometimes a non-improving move must be performed to keep the search going. Examples of these techniques are tabu search [3] and simulated annealing [4]. Our results apply to basic local search but can be readily adapted to use in more sophisticated procedures such as tabu search. This, however, is beyond the scope of this paper.