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 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 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. Large 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.

Combinatorial optimization problems are difficult to solve due to the space explosion in an exhaustive search. Using Ising model-based solvers can efficiently find near-optimal solutions by minimizing the energy of a nonlinear Hamiltonian system. In contrast to Ising machines based on quantum mechanics, classical Ising machines using conventional technologies, such as the complementary metal-oxide-semiconductor, offer efficient implementations with competitive performance. In this paper, we briefly review recently developed simulation algorithms of classical Ising machines. These algorithms are classified by considering various inherent mechanisms in the simulation of physical phenomena. Then, strategies to improve the simulation efficiency are discussed by generalizing their characteristics and behaviours. These simulation algorithms are key for improving the efficiency of classical Ising machines in solving combinatorial optimization problems.