Graph Neural Network architecture to solve the decision variant of the Traveling Salesperson Problem (i.e. "is there a Hamiltonian tour in G with up to a given cost"?).

OBS. To run this code you must install pyconcorde first.

Upon training with -2%, +2% from the optimal cost, the model is able to achieve >80% test accuracy. It also learns to generalize for different graph distributions & larger instance sizes (with decreasing accuracy) and more relaxed deviations (with better accuracy).

The results from this experiment are reported in the research paper "Learning to Solve NP-Complete Problems -- A Graph Neural Network for the Decision TSP" by M. Prates, P. Avelar, H. Lemos, L. Lamb and M. Vardi, which has been accepted for presentation at AAAI 2019. It is available as a arXiv.org.