Clustering Approach for Solving Traveling Salesman Problems via Ising Model Based Solver
Dan Akira, Riu Shimizu, Takeshi Nishikawa, Song Bian, Takashi Satō
Abstract
Ising model based solver have gained increasing attention due to their efficiency in finding approximate solutions for combinatorial optimization problems. However, when solving doubly constrained problems, such as traveling salesman problem using the Ising model-based solver, both the execution speed and the quality of solutions deteriorate significantly due to the quadratically increasing spin counts and strong constraints placed on the spins. In this paper, we propose a recursive clustering approach that accelerates the calculations of the Ising model and that also helps to obtain high-quality solutions. Through evaluations using the TSP benchmarks, the qualities with the proposed method have been improved by up to 67.1% and runtime were reduced by 73.8x.