Comment by Animats

10 hours ago

If you just use the simple-minded Bell Labs probabilistic algorithm, how much worse is that result?

The classic TSP approach is:

1. Hook up all the nodes in some arbitrary path.

2. Cut the path in two places to create three pieces.

3. Rearrange those three pieces in the six possible ways and keep the shortest.

4. Iterate steps 2-3 until no improvement has been observed for a while.

This is not guaranteed to be optimal, but for most real-world problems either finds the optimal result or is very close.

6 comments

Animats

amscanne 10 hours ago

Note that the tour itself was found quickly using a heuristic solver (https://www.math.uwaterloo.ca/tsp/korea/computation.html), the achievement here and all the computation is to establish that this is the lower bound (assuming I understood correctly).

So, the heuristic solver worked pretty darn well :) Although, I’m not sure how close it would have been the heuristic algorithm you are describing (I suspect that it is considerably more advanced for good reasons, randomly picking will take too long to converge).

n4r9 9 hours ago
The algorithm that OP describes is more commonly known as 2-opt [0]. The heuristic used in this case is referred to as LKH which I assume means the Lin-Kernighan Heuristic [1]. The latter is sort of a meta generalisation of the former.
[0] https://en.m.wikipedia.org/wiki/2-opt
[1] https://en.m.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuris...
- vjerancrnjak 9 hours ago
  
  2-opt is a bit simpler.
  LKH is a bit different, refers to Lin-Kernighan+Helsgaun -- http://webhotel4.ruc.dk/~keld/research/LKH/

neves 5 hours ago

https://www.youtube.com/watch?v=tChnXG6ulyE

Author's presentation about it

yobbo 9 hours ago

Iirc the (probably simplified) LKH heuristic they used:

  For each iteration:
     apply some randomisation
     starting at each place
         cut the path in 2..n places
           reconnect in the most optimal way 
           if the new tour is the new best, save

n is a small number like 4 maybe 5?

vjerancrnjak 9 hours ago

2-opt: [a, b, ..., d, e]
reversing subarray from b to d is a 2-opt move.
3-opt (1 particular move):
a b c d e f
a e d c b f -- reversal from b to e
a e d b c f -- reversal from c to b
LK heuristic is a bit more involved, but focuses on continuing to reverse the subarray on the [b, ..., d] segment, with search and backtracking involved. (I think that's refered to as sequential k-opt moves, but I think it's already quite hard to know what exactly LK is, and LKH does much more)
By focusing on the subarray, assuming distance symmetry (length from b to e is same as length from e to b, but there are correct workarounds if this does not hold), you can evaluate the cost of the new route in constant time (but with bigger k there's more moves to evaluate https://oeis.org/A001171)