The Transformer Network for the Traveling Salesman Problem
1–10 of 22 posts
Re: The Transformer Network for the Traveling Salesman Problem
#2"We report improved performances over recent learned heuristics with an optimal gap of 0.004% for TSP50 and 0.39% for TSP100."
Complexity: O(n^2)
Re: The Transformer Network for the Traveling Salesman Problem
#3"We report improved performances over recent learned heuristics with an optimal gap of 0.004% for TSP50 and 0.39% for TSP100." Complexity: O(n^2)
According to the website below, the DP solution is O(n^2 * 2^n). That would be a big speedup.
https://www.geeksforgeeks.org/travelling-salesman-problem-se...
Re: The Transformer Network for the Traveling Salesman Problem
#4"We report improved performances over recent learned heuristics with an optimal gap of 0.004% for TSP50 and 0.39% for TSP100." Complexity: O(n^2)
If true, what implications does this have for P = NP? My intuition for a long time has been that P = NP only in the limit of an "infinitely sophisticated" algorithm. Such that as we do more research (or I suppose train larger models), we get closer and closer to the polynomial ideal.
Re: The Transformer Network for the Traveling Salesman Problem
#5"We report improved performances over recent learned heuristics with an optimal gap of 0.004% for TSP50 and 0.39% for TSP100." Complexity: O(n^2)
If true, what implications does this have for P = NP? My intuition for a long time has been that P = NP only in the limit of an "infinitely sophisticated" algorithm. Such that as we do more research (or I suppose train larger models), we get closer and closer to the polynomial ideal.
Doesn't apply here because this algorithm is an approximate TSP.
Re: The Transformer Network for the Traveling Salesman Problem
#6For context, the tests here are performed on 50- and 100-city instances, as they are limited by current GPU memory sizes. Meanwhile, the best heuristic code for TSP [1] frequently provides optimal solutions to 100k-city instances ("heuristic" = no optimality guarantee, like what this paper proposes; but one can then seek a proof of optimality if desired using a slower "exact" algorithm).
Also, Dantzig, Fulkerson and Johnson solved a 50-city TSP to optimality, with an exact method, by hand, in 1954 [2]. The practical running time was slower than what is proposed here, admittedly :-).
This is not a criticism of the paper, though: To their credit, the authors are quite straightforward about this, they're not trying to hide it. Their point is to demonstrate that their machine learning approach has potential.
Re: The Transformer Network for the Traveling Salesman Problem
#7"We report improved performances over recent learned heuristics with an optimal gap of 0.004% for TSP50 and 0.39% for TSP100." Complexity: O(n^2)
If true, what implications does this have for P = NP? My intuition for a long time has been that P = NP only in the limit of an "infinitely sophisticated" algorithm. Such that as we do more research (or I suppose train larger models), we get closer and closer to the polynomial ideal.
[deleted]
Re: The Transformer Network for the Traveling Salesman Problem
#8"We report improved performances over recent learned heuristics with an optimal gap of 0.004% for TSP50 and 0.39% for TSP100." Complexity: O(n^2)
If true, what implications does this have for P = NP? My intuition for a long time has been that P = NP only in the limit of an "infinitely sophisticated" algorithm. Such that as we do more research (or I suppose train larger models), we get closer and closer to the polynomial ideal.
Current best heuristics, Lin-Kernighan-Helsgaun arrive probabilistically at better percentages for TSP.
Definitely makes you wonder if P = NP is even relevant when all the interesting instances can be solved to optimality or very near to it extremely often.
Re: The Transformer Network for the Traveling Salesman Problem
#9For context, the tests here are performed on 50- and 100-city instances, as they are limited by current GPU memory sizes. Meanwhile, the best heuristic code for TSP [1] frequently provides optimal solutions to 100k-city instances ("heuristic" = no optimality guarantee, like what this paper proposes; but one can then seek a proof of optimality if desired using a slower "exact" algorithm). Also, Dantzig, Fulkerson and…
> best heuristic code for TSP .. 100k-city instances
These "best cases" are hand-tuned for the domain by algorithm experts - right? How big is the performance jump from generic z3 or whatever?
Edit: After alphazero, there was lots of chatter about improving combinatorical problems. This has proven elusive.
Re: The Transformer Network for the Traveling Salesman Problem
#10I'd like to see how it performs on trivial instances like a NxM grid of points (perhaps with small perturbations).