One of the vital roles of computing is to solve large-scale combinatorial optimization problems in a short time. In recent years, methods have been proposed that map optimization problems to ones of searching for the ground state of an Ising model by using a stochastic process. Simulated annealing (SA) is a representative algorithm. However, it is inherently difficult to perform a parallel search. Here we propose an algorithm called momentum annealing (MA), which, unlike SA, updates all spins of fully connected Ising models simultaneously and can be implemented on GPUs that are widely used for scientific computing. MA running in parallel on GPUs is 250 times faster than SA running on a modern CPU at solving problems involving 100 000 spin Ising models.
One of the vital roles of computing is to solve large-scale combinatorial optimization problems in a short time. In recent years, methods have been proposed that map optimization problems to ones of searching for the ground state of an Ising model by using a stochastic process. Simulated annealing (SA) is a representative algorithm. However, it is inherently difficult to perform a parallel search. Here we propose an algorithm called momentum annealing (MA), which, unlike SA, updates all spins of fully connected Ising models simultaneously and can be implemented on GPUs that are widely used for scientific computing. MA running in parallel on GPUs is 250 times faster than SA running on a modern CPU at solving problems involving 100 000 spin Ising models.
This research is concerned with an annealing processor for efficiently solving a combinatorial optimization problem.\nIn order to realize a smart society, optimization of people and thingssuch as transportation networks, power networks, human resource allocationand routes is indispensable. Many of these problems are called combinatorial optimization problems and are known as very important problems in modern society. However, it is known that the combinatorial optimization problem is NP-hard and it is difficult to efficiently solve it with a conventional Neumann computer.\nIn recent years, the miniaturization of the process of manufacturing computer chips is approaching the physical limit. Therefore, especially in the solution by the full search, the improvement in speed due to the calculation speed of the computer cannot be expected. From such a background, dedicated hardware capable of solving a combination optimization problem at high speed and with low power consumption has been attracting attention.\nThe annealing processor is a general-purpose combination optimization solver that utilizes the property that the ground state of the optimization problem expressed by using the Ising model and the optimal solution of the combination optimization problem match. The Ising model is a ferromagnetic model in statistical physics expressed by spins having an upward and downward state, spin-spin interactions occurring between the spins, and an external magnetic field acting on each spin. The Ising model can express a combinatorial optimization problem by expressing a control target and a cost using these parameters. The annealing processor updates the spin state while slowly lowering the temperature parameters based on simulated annealing,which is an optimization method learned from natural phenomena generally called annealing. Eventually, the spin will reach the ground state with a high probability and obtain the optimal solution.\nAnnealing processors are classified into two types, the nearest neighbor type and the fully connected type, depending on the shape of the Ising model simulated on the hardware. In the nearest neighbor type, the coupling between spins is limited to only between adjacent spins, and in the full coupling type, coupling exists between arbitrary spins. The nearest neighbor type realizes high parallel processing by reducing the data spin required by simulated annealing by reducing the proximity spin. In addition, since data transfer is limited to adjacent spins, the scalability is high. However, since the spin-to-spin interaction is sparse, there is a problem that the class of combinatorial optimization problems that can be dealt with is limited, or that the problem requires deformation processing to match the Ising model of hardware. The fully connected type can solve any class of problems as long as the number of spins permits, however it requires connections between arbitrary spins.Therefore, scalability is low. Because there there is a dependency on all spins,the number of spins that can be updated at one time is always limited to only one regardless of the total number of spins. Therefore, it takes time to converge to the ground state.\nIn this research, we propose a method of increasing the number of spins for this annealing processor by using (1) a spatially-expanded time-division processing mechanism architecture based on a loosely-coupled type, (2) An algorithm for applying a fully coupled Ising network to a more complex Ising network using the nearest neighbor Ising network and an annealing method that can be updated in parallel, (3)We conducted a study on the architecture of a fully coupled annealing processor for parallel updating annealing.\nAs described above, the research described in this paper contributes to the improvement of the efficiency of the annealing processor for solving the large-scale combinatorial optimization problem from both the fundamental algorithm and the hardware architecture. I hope that this research will solve the combinatorial optimization problem that is expected to increase in demand in the future and contribute to the development of human society.
Combinatorial optimization problems are frequently classified as NP-hard, which means that the time needed to find the optimal solution generally increases exponentially with the problem size. However, the existing research gap highlights the necessity to develop combinatorial optimization methods capable of scaling to large problems while maintaining low solution latency. In this paper, we introduce stochastic simulated quantum annealing (SSQA) for fast solution of combinatorial optimization problems. SSQA is designed based on stochastic computing, which can simulate quantum annealing (QA) by using multiple replicas of spins (probabilistic bits) in classical computing. The use of stochastic computing leads to an efficient parallel spin-state update algorithm, enabling quick search for a solution around the global minimum energy. Therefore, SSQA realizes quantum-like annealing for large-scale problems and can handle fully connected models in combinatorial optimization, unlike QA. The proposed method is evaluated in MATLAB on graph isomorphism problems, which are typical combinatorial optimization problems. It can handle a 100-times larger problem size compared to QA and a 25-times larger problem size compared to a traditional SA method, respectively, for similar convergence probabilities. The time to solution of SSQA is 11.5 times and 423 times smaller than that of the conventional stochastic simulated annealing method and traditional SA, respectively, when solving a 2,025-node combinatorial optimization problem.
Ising machines are domain-specific computers that solve combinatorial optimization problems (COPs). They utilize an Ising model to represent a COP and search for the optimal spin configuration of the Ising model to solve the COP. Most Ising machines are based on simulated annealing (SA) and update the spin configuration according to single-spin-flip Markov Chain Monte Carlo methods. However, supporting a multi-spin flip is important to enhance the search performance of SA-based Ising machines when constrained COPs are solved. In this paper, we extend the merge method, which was introduced to provide a multi-spin-flip capability for SA-based Ising machines, and formulate it as a series of matrix multiplications that can be executed on a graphics processing unit (GPU) efficiently. We then construct a GPU-based Ising machine that implements the GPU-oriented merge method together with an extended SA algorithm. We finally demonstrate its superiority over the state-of-the-art GPU-based Ising machine for quadratic knapsack problems.
Annealing processors that can quickly solve combinatorial optimization problems (COPs) are attracting attention. They solve COPs by converting them into spin-spin interactions and external fields of the Ising model. Annealing processors that use fully-coupled spin coupling can solve a wide range of COPs. However, it is difficult to execute parallel annealing in fully-coupled spin coupling because one spin is updated by referring to all the other spins. In this paper, we proposed multi-state pseudo annealing (MSPA), which is an annealing method for changing the spin value from a conventional binary to a multi state that takes into account intermediate states. In a software validation, we solved the Maxcut problem and the traveling salesman problem and confirmed that the proposed method improves the solution quality in parallel annealing compared with simulated annealing and pseudo annealing. In addition, we implemented MSPA on a field-programmable gate array as a 1024 -spin 16 -parallel system using a scalable structure. With the proposed system, we solved the Max-cut problem and confirmed that it achieves a 9.40 times faster solving speed and yields a 1% larger Max-cut value compared with the conventional parallelized annealing processors.
Simulated quantum annealing (SQA) is a probabilistic approximation method to find a solution for a combinatorial optimization problem using digital computers. The processing time of SQA increases exponentially with the number of variables. Therefore, acceleration of SQA is regarded as a very important topic. However, parallel implementation is difficult due to the serial nature of the quantum Monte Carlo algorithm used in SQA. In this paper, we propose a method to implement SQA in parallel on a GPU while preserving the data dependency. According to the experimental results, we have achieved over 97 times speed-up while maintaining the same accuracy-level compared to a single-core CPU implementation.
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.