The Transformer Network for the Traveling Salesman Problem

Post by gopiandcode » Sun, Mar 21, 2021, 12:37 PM UTC

alfiedotwtf wrote: post #20

thxg wrote: post #6

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…

Provably optimal? I thought TSP was NP-Hard and could only ever be solved via heuristics

NP-hard refers to solving the problem in the general case - for a given specific instance it may be possible to find an optimal solution more easily by exploiting specific features of the graph (for instance, a series of nodes arranged in a ring would have a trivial optimal solution).

Post by UncleMeat » Sun, Mar 21, 2021, 12:39 PM UTC

knuthsat wrote: post #8

mpoteat wrote: post #4

Earlier quoted context omitted.

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.

Some NP-complete problems have provably bad approximations if P!=NP. You don't get the same polynomial reduction behavior if you are using approximation algorithms. So for some problems we may have utterly practical algorithms and for others we never will (assuming P!=NP).

Re: The Transformer Network for the Traveling Salesman Problem

Re: The Transformer Network for the Traveling Salesman Problem