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
    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
    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
    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
    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
    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
    Nov 5, 2019 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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