Evaluation   
We compare models on a held-out test set of 25,600 TSP samples, consisting of 1,280 samples each of TSP10, TSP20, \(\dots \) , TSP200.
Our evaluation metric is the optimality gap w.r.t. the Concorde solver, i.e. the average percentage ratio of predicted tour lengths relative to optimal tour lengths.
To compare design choices among identical models, we plot line graphs of the optimality gap as TSP size increases (along with a 99%-ile confidence interval) using beam search with a width of 128.
Compared to previous work which evaluated models on fixed problem sizes [1]}, [2]}, [3]}, our evaluation protocol identifies not only those models that perform well on training sizes, but also those that generalize better than non-learnt heuristics for large instances which are intractable to train on.
<FIGURE>