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