IDEQ: an improved diffusion model for the TSP
This work addresses the TSP, a classic combinatorial optimization problem, with a neural-based method that shows competitive performance against established heuristics, though it is incremental over prior diffusion models like DIFUSCO and T2TCO.
The paper tackles the Traveling Salesman Problem (TSP) by proposing IDEQ, an improved diffusion model that enhances solution quality by leveraging the constrained state space and modifying training objectives. The result is a new state-of-the-art for neural network-based methods, achieving optimality gaps of 0.3% on 500-city instances and 0.5% on 1000-city instances, and matching or outperforming the best heuristics like LKH3 on some benchmark instances.
We investigate diffusion models to solve the Traveling Salesman Problem. Building on the recent DIFUSCO and T2TCO approaches, we propose IDEQ. IDEQ improves the quality of the solutions by leveraging the constrained structure of the state space of the TSP. Another key component of IDEQ consists in replacing the last stages of DIFUSCO curriculum learning by considering a uniform distribution over the Hamiltonian tours whose orbits by the 2-opt operator converge to the optimal solution as the training objective. Our experiments show that IDEQ improves the state of the art for such neural network based techniques on synthetic instances. More importantly, our experiments show that IDEQ performs very well on the instances of the TSPlib, a reference benchmark in the TSP community: it closely matches the performance of the best heuristics, LKH3, being even able to obtain better solutions than LKH3 on 2 instances of the TSPlib defined on 1577 and 3795 cities. IDEQ obtains 0.3% optimality gap on TSP instances made of 500 cities, and 0.5% on TSP instances with 1000 cities. This sets a new SOTA for neural based methods solving the TSP. Moreover, IDEQ exhibits a lower variance and better scales-up with the number of cities with regards to DIFUSCO and T2TCO.