3 ms·

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 s

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.

amscanne 2y ago
Note that the tour itself was found quickly using a heuristic solver (https://www.math.uwaterloo.ca/tsp/korea/computation.html 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 2y 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 https://en.m.wikipedia.org/wiki/2-opt [1] https://en.m.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristic https://en.m.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuris...
  - vjerancrnjak 2y ago
    2-opt is a bit simpler. LKH is a bit different, refers to Lin-Kernighan+Helsgaun -- http://webhotel4.ruc.dk/~keld/research/LKH/ http://webhotel4.ruc.dk/~keld/research/LKH/
yobbo 2y 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 2y 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 https://oeis.org/A001171)
neves 2y ago
https://www.youtube.com/watch?v=tChnXG6ulyE https://www.youtube.com/watch?v=tChnXG6ulyE Author's presentation about it

amscanne 2y ago

Note that the tour itself was found quickly using a heuristic solver (https://www.math.uwaterloo.ca/tsp/korea/computation.html 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 2y 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 https://en.m.wikipedia.org/wiki/2-opt [1] https://en.m.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristic https://en.m.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuris...
- vjerancrnjak 2y ago
  2-opt is a bit simpler. LKH is a bit different, refers to Lin-Kernighan+Helsgaun -- http://webhotel4.ruc.dk/~keld/research/LKH/ http://webhotel4.ruc.dk/~keld/research/LKH/

yobbo 2y 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 2y 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 https://oeis.org/A001171)

neves 2y ago

https://www.youtube.com/watch?v=tChnXG6ulyE https://www.youtube.com/watch?v=tChnXG6ulyE Author's presentation about it