[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)