# Why doesn't 2-opt return an optimal solution?

To find a solution for the Traveling Salesman Problem (TSP), one way to go is an algorithm called 2-opt, which is explained below.

The 2-opt algorithm basically removes two edges
from the tour, and reconnects the two paths created.
This is often refered to as a 2-opt move. There is only
one way to reconnect the two paths so that we still
have a valid tour (figure 1).  We do this only if the
new tour will be shorter. Continue removing and re-
connecting the tour until no 2-opt improvements can
be found. The tour is now 2-optimal.


For me, this algorithm tries all possibilities for edge combinations, so it should return the best (optimal) solution, right? Wrong, because :

If we look at the tour as a permutation of all the
cities, a 2-opt move will result in reversing a segment
of the permutation.
Running the 2-opt heuristic will often result in a tour
with a length less than 5% above the Held-Karp bound.


My question is ; why does it not return the optimal solution? Does it not try all possible edge combinations? Can you give an example graph for which 2-opt doesn't give an optimal solution? I'm citing from here : https://web.tuke.sk/fei-cit/butka/hop/htsp.pdf

• You can give such an example. Just try a few graphs. This heuristic is known as local search. You start with some solution and then make local improvements, until you get stuck at a local optimum. A local optimum need not be a global optimum. – Yuval Filmus Apr 11 '17 at 8:11
• A concrete example can be found here. See also this paper, which mentions an $\Omega(\sqrt{n})$ lower bound and proves a matching $O(\sqrt{n})$ upper bound. – Yuval Filmus Apr 11 '17 at 8:17
• @YuvalFilmus which one is the example? figure 3? because in figure 3, the path chosen can be shorter by using 2-opt if I'm not mistaken... – J. Schmidt Apr 11 '17 at 9:28
• @YuvalFilmus I posted an answer following your advice to try some graphs, can you correct me in it if needed? – J. Schmidt Apr 11 '17 at 10:29
• The paper gives an example in which the second best tour differs from the best one in many edges. In particular, it is a local optimum for any local search only considering moves affecting fewer edges. – Yuval Filmus Apr 11 '17 at 23:43