IDEQ: an improved diffusion model for the TSP

Recent years have seen a surge in machine learning models to solve combinatorial optimization (CO) problems. The field of combinatorial optimization is a historical field of research and application in computer science. After decades of progress, very efficient algorithms exist to provide exact solutions or approximate solutions to many CO problems. The Traveling Salesman Problem (TSP) stands as a prominent example of this fact: the TSP is very appealing as it is very simple to understand, it has a wide range of applications, and we are able to solve exactly rather large instances of this problem on a mere laptop (an instance defined over a few thousands cities can be solved within one hour), and we have approximate algorithms that are able to find tours that are very close to optimality (LKH3 [4] can solve instances of 40,000 cities in about one hour on a laptop but we have no guarantee that the result is optimal). These facts can not be forgotten when we try to propose alternate approaches to solve the TSP. Because of its appeal, the TSP has also drawn the attention of researchers in deep neural networks in the recent years. If the first attempts had difficulties solving even small TSP instances of a dozen cities, progress has been made. In this paper, we build on these previous works and go a step further.