An Ising Machine based on an Improved Parallel Annealing Algorithm for Solving Traveling Salesman Problems

• Author / Creator

  Tao, Qichao

• Annealing-based Ising machines have shown promising results in solving combinatorial optimization problems. As a typical class of these problems, however, traveling salesman problems (TSPs) are very challenging to solve due to the constraints imposed on the solution. This thesis 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 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 digital annealing (DA) and momentum annealing (MA), the IPA reduces the run time by 44.4 times and 19.9 times for a 14-city TSP, respectively. Larger scale TSPs can be more efficiently solved by taking a k-medoids clustering approach that decreases the average travel distance of a 22-city TSP by 51.8% compared with DA and by 42.0% compared with MA. This approach groups neighboring cities into clusters to form a reduced TSP, which is then solved in a hierarchical manner by using the IPA algorithm on each cluster.
  Furthermore, an Ising machine that implements this annealing algorithm is designed by using a half-precision floating-point representation of the coefficients in the Ising model. This design reuses adders in the local field accumulator units (LAUs) for variable calculation and approximates the momentum scaling factor by a linear increment to save hardware. Approximate arithmetic is considered in the design for improving the speed of accumulation in the LAUs. A hybrid approximation method using lower-part-OR truncated adders (LOTAs) is applied and shown to reduce the delay of the circuit by 3.8% at the cost of an increase in average travel distance
  by 1.9%. Finally, an IPA-based Ising machine prototype with 64 spins is built and synthesized by using the Synopsys Design Compiler. Using a 28-nm CMOS process with a supply voltage of 1.0 V, a temperature of 25 ◦C, and a clock frequency of 200 MHz, the total area of the circuit is 6.262 mm2, the power dissipation is 41.108 mW, and the delay is 3.82 ns. Compared with other designs, the area and power dissipation of this circuit are larger due to the implementation of a half-precision floating-point representation. However, the IPA-based Ising machine is expected to solve more complicated problems and improve the solution quality.

• Subjects / Keywords

  • Ising machine
  • combinatorial optimization
  • traveling salesman problem
  • simulated annealing

• Graduation date

  Fall 2022

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-t4f8-qd68

• License

  This thesis is made available by the University of Alberta Library with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.