Solving Traveling Salesman Problems via a Parallel Fully Connected Ising Machine
TimeThursday, July 14th4:50pm - 5:10pm PDT
Location3005, Level 3
Event Type
Research Manuscript
Emerging Models of Computation
DescriptionThis article proposes a parallel annealing algorithm for a fully connected Ising machine that significantly
improves the accuracy and performance in solving constrained combinatorial optimization problems such as the traveling salesman problem (TSP). Unlike previous parallel annealing algorithms, this improved parallel annealing (IPA) algorithm efficiently solves TSPs using an exponential temperature function with a dynamic offset. Compared with conventional digital annealing, the IPA algorithm reduces the run time by 13.5 times for a 14-city TSP. Large scale TSPs can be more efficiently solved by taking a clustering approach that further increases the solution accuracy by 17%.