The Direction Convention That Tour Cost Hides in Neural TSP Solvers

Neural solvers for the traveling salesman problem are compared by the cost of their tours, but one of their choices is invisible to that cost: the direction of travel. A tour and its reverse cost the same, yet on our 1,024 test instances with 100 cities, greedy POMO constructs every tour clockwise and Sym-NCO every tour counterclockwise. We call the direction in which a model constructs its tours its convention. We give a model the first cities of an optimal tour, a prefix, traveled clockwise or counterclockwise, and let it complete the tour. With 15 cities left, POMO and Sym-NCO complete it almost optimally with their convention and, against it, worse than when they construct whole tours. LEHD and BQ-NCO, whose tours cost within a fraction of a percent of POMO's, have no convention and complete closer still to optimal in both directions. One part of the score with which POMO and Sym-NCO pick the next city, the priority, ranks the cities left largely in the order of each model's own tours. On a given input, the priority depends only on which cities are left, so it ranks them the same from either endpoint of the prefix. Against the convention, where removing the priority changes the first choice, the priority usually favors the city whose optimal completion costs more. The priority thus shows one place where, in models that encode the cities once, the convention enters a choice. Models that are handed a prefix should therefore be tested in both directions.