Processor Architecture and Systems Synthesis Laboratory

Dan, a graduate of our group presented his research at the 57th ACM/IEEE Design Automation Conference (DAC) 2020 held from July 20 to July 24, 2020 (presentation date: July 25). In addition to DAC being the top conference in integrated circuit design, this year’s conference was completely virtual due to the influence of the new coronavirus, so the number of participants was much larger than previous years.

Dan’s presentation is about acceleration of the Traveling Salesman Problem (TSP), a widely known combinatorial optimization problem, by using an Ising model solver. The Ising model is a model that mimics the properties of ferromagnetic materials, using spins that interact with their neighbors. It has recently attracted greater attention because of its potential to solve various optimization problems in a highly parallel manner. However, when mapping an optimization problems to the Ising model, as in the case of TSP, it is necessary to take into account the interactions between many (or in the case of TSP, all) spins. The quality of the solution hence becomes insufficient, and the computation time will also becomes larger. In this paper, we propose a method for finding the shortest path using the Ising model solver while recursively clustering cities, taking into account the fact that in TSP, the moves between distant cities do not need to be considered when finding the shortest path. We show that by reducing the interaction between spins, the quality of the TSP solution can be improved and the computation can be accelerated substantially.

• Akira Dan, Riu Shimizu, Takeshi Nishikawa, Song Bian and Takashi Sato, “Clustering approach for solving traveling salesman problems via Ising model based solver,” in Proc. ACM/IEEE Design Automation Conference (DAC), pp.26.1:1-26.1:6, July 2020.