5
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Apr 11, 2017 at 8:11
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Apr 11, 2017 at 8:17
  • $\begingroup$ @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... $\endgroup$
    – J. Schmidt
    Commented Apr 11, 2017 at 9:28
  • $\begingroup$ @YuvalFilmus I posted an answer following your advice to try some graphs, can you correct me in it if needed? $\endgroup$
    – J. Schmidt
    Commented Apr 11, 2017 at 10:29
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Apr 11, 2017 at 23:43

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

In reality, 2-opt might actually give you the optimal solution in fact odds are good that it very often does. But, to prove this requires brute force NP-complete travelling salesman solution. So it might give you the best solution for a particular dataset but you can't know this is optimal rather than pareto-optimal without an NP-complete operation.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Of course, brute force is not the only exact algorithm for TSP. I think it's also quite optimistic to say that 2-opt often gives you an optimal solution; depends heavily. $\endgroup$
    – Juho
    Commented Nov 5, 2019 at 17:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.