MESCO: Learning to Solve Large-Scale TSP with Self-Supervision via MCTS Ensembles

Many neural methods for solving the Traveling Salesman Problem (TSP) follow the heatmap-guided Monte Carlo Tree Search (MCTS) paradigm, in which a neural network assigns a probability to each edge and MCTS uses those probabilities to guide an improvement search. The strongest of such methods train on solved TSP instances, but at scale this supervision becomes a bottleneck: exact solvers are intractable beyond a few thousand nodes, and even heuristic solutions cost over an hour per instance at 10,000 nodes. This cost of supervision, rather than model capacity, appears to be the limit, as a recent study found that at 10,000 nodes, a simple heuristic heatmap beats every neural method, including supervised methods. To address the challenge of scale, we introduce MESCO, which derives supervision from an ensemble of short MCTS rollouts run during training. Each rollout follows the model's current heatmap, samples its own search configuration, and runs for a fixed budget instead of a solve time dictated by the instance. Aggregating the edges selected by the rollouts, weighted by the quality of the solutions they produce, yields a heatmap target that is more informative than any individual rollout's tour, and improves as the model does. To our knowledge, MESCO is the first neural heatmap method to place MCTS inside the training loop. MESCO attains the best reported optimality gaps on TSP problems with 1,000 and 10,000 nodes, $0.51$% and $1.10$%, and is competitive with supervised methods at 500 nodes with a gap of $0.22$%, while reducing the cost of supervision by up to $192\times$.