[HN Gopher] The Transformer Network for the Traveling Salesman P... ___________________________________________________________________ The Transformer Network for the Traveling Salesman Problem Author : djoldman Score : 18 points Date : 2021-03-20 20:29 UTC (2 hours ago) (HTM) web link (arxiv.org) (TXT) w3m dump (arxiv.org) | amelius wrote: | I'd like to see how it performs on trivial instances like a NxM | grid of points (perhaps with small perturbations). | djoldman wrote: | "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) | greesil wrote: | 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... | mpoteat wrote: | 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] | knuthsat wrote: | 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. | visarga wrote: | Doesn't apply here because this algorithm is an approximate | TSP. | thxg wrote: | For 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. | | [1] http://webhotel4.ruc.dk/~keld/research/LKH/ | | [2] http://www.math.uwaterloo.ca/tsp/uk/history.html | algo_trader wrote: | > 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. ___________________________________________________________________ (page generated 2021-03-20 23:00 UTC)