Can neural networks efficiently solve the traveling salesmen problem?

Question

Can neural networks efficiently solve the traveling salesmen problem? Are there any research papers that show that neural networks can solve the TSP efficiently?

The TSP is an NP-hard problem, so I suspect that there are only approximate solutions to this problem, even with neural networks. So, in this case, how would efficiency be defined?

In this context, it seems that the time efficiency may be obtained by resource inefficiency: by making the neural network enormous and simulating all the possible worlds, then maximizing. So, while time to compute doesn't grow much as the problem grows, the size of the physical computer grows enormously for larger problems; how fast it computes is then, it seems to me, not a good measure of the efficiency of the algorithm in the common meaning of efficiency. In this case, the resources themselves only grow as fast as the problem size, but what explodes is the number of connections that must be built. If we go from 1000 to 2000 neurons to solve a problem twice as large and requiring exponentially as much time to solve, the algorithms requiring only twice as many neurons to solve in polynomial time seem efficient, but, really, there is still an enormous increase in connections and coefficients that need be built for this to work.

Is my above reasoning incorrect?

Answer 1

To the best of my knowledge, there isn't any difference between the algorithmic methods and the NN methods. Those that can solve in polynomial time do not give a precise solution. Those that do give a precise solution do not solve in polynomial time. Of those that give a precise solution, the fastest takes $2^N$, but it blows up in terms of memory. The fastest good algorithm I believe is Concorde.

The efficient algorithms solve in polynomial time, don't blow up in terms of memory, and give a solution close to perfect, say, within 2-3%. Again, to the best of my knowledge, no NN has beaten the best algorithmic solutions, but there are suggestions that some NN solution could be faster.

Answer 2

There is some recent work addressing this issue, to learn the conditional probability of an output sequence with elements that are discrete tokens corresponding to positions in an input sequence. See Pointer Networks.