HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whyoptimalreturnoptdoesnsolution

Problem

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

Solution

I think I understand now after trying some examples as Yuval Filmus suggested. In the example below, we can get stuck on the local optimum using 2-opt, but as we can see the global optimum is better.

Context

StackExchange Computer Science Q#73784, answer score: 6

Revisions (0)

No revisions yet.