Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Research on Annealing Processors for Large-Scale Combinatorial Optimization Problems

佳生 山本

Published Mar 25, 2020• 1 citation
Publisher

Abstract

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.

DOI
10.14943/doctoral.k14133

Related papers

Binary optimization by momentum annealing

Takuya Okuyama, Tomohiro Sonobe, Ken‐ichi Kawarabayashi +1 more

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.

Physical review. E•Jul 10, 2019•92 citations

7.3 STATICA: A 512-Spin 0.25M-Weight Full-Digital Annealing Processor with a Near-Memory All-Spin-Updates-at-Once Architecture for Combinatorial Optimization with Complete Spin-Spin Interactions

Kasho Yamamoto, Kota Ando, Normann Mertig +6 more

Combinatorial optimization problems ubiquitously appear in AI applications, e.g. machine learning, operational planning, drug discovery, etc. Yet, their NP-hardness makes them notoriously difficult to solve on present computers. To address this problem, new hardware architectures [1, 4], called annealers, have emerged in recent years. Annealers exploit the fact that combinatorial optimization problems can be mapped to the ground state search of an Ising model, where the combination of N spins (σ- ∈ f-1}. x=1, ...,N) with lowest Ising energy represents the optimal solution to the problem (Fig. 7.3.1).

Digest of technical papers/Digest of technical papers - IEEE International Solid-State Circuits Conference•Feb 1, 2020•73 citations

30.4 A Fully Integrated Annealing Processor for Large-Scale Autonomous Navigation Optimization

Yi‐Chen Chu, Yu‐Cheng Lin, Yu-Chen Lo +1 more

Autonomous navigation serves as a versatile technology prominently used in logistics and transportation. The application of automatic guided vehicles has become pervasive within the realm of factory automation, as shown in Fig. 30.4.1. For such applications, path planning and collision avoidance are two main tasks. Both tasks are classified as combinatorial optimization problems (COPs), and finding their optimal solutions is time-consuming [1]. A COP can be mapped to an Ising model with spin couplings based on the nature of the problem. Annealing is then applied to find the solution by iteratively updating spins until the states of the spins reach the lowest energy (known as a Hamiltonian). Digital annealers [2] –[4] have been demonstrated to accelerate solving COPs with exponential complexity. Some designs [2] [3] only support small-scale COPs because of the limited number of spins. The other [4] can solve larger problems, while the problem complexity is still limited by their sparse spin connections. Mapping a COP onto an Ising model and vice versa is necessary for solving a specific problem, which is also not addressed in the previous hardware digital annealers.

Digest of technical papers/Digest of technical papers - IEEE International Solid-State Circuits Conference•Feb 18, 2024•15 citations

Efficient Implementation of Parallel Annealing Method with Heisenberg Model

Kazuma Kanai, T. Kawahara

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.

IEEE Asia Pacific Conference on Circuits and Systems (APCCAS)•Nov 7, 2024•2 citations

A Fully-Connected Ising Model Embedding Method and Its Evaluation for CMOS Annealing Machines

Daisuke Oku, Kotaro Terada, Masato HAYASHI +3 more

Combinatorial optimization problems with a large solution space are difficult to solve just using von Neumann computers. Ising machines or annealing machines have been developed to tackle these problems as a promising Non-von Neumann computer. In order to use these annealing machines, every combinatorial optimization problem is mapped onto the physical Ising model, which consists of spins, interactions between them, and their external magnetic fields. Then the annealing machines operate so as to search the ground state of the physical Ising model, which corresponds to the optimal solution of the original combinatorial optimization problem. A combinatorial optimization problem can be firstly described by an ideal fully-connected Ising model but it is very hard to embed it onto the physical Ising model topology of a particular annealing machine, which causes one of the largest issues in annealing machines. In this paper, we propose a fully-connected Ising model embedding method targeting for CMOS annealing machine. The key idea is that the proposed method replicates every logical spin in a fully-connected Ising model and embeds each logical spin onto the physical spins with the same chain length. Experimental results through an actual combinatorial problem show that the proposed method obtains spin embeddings superior to the conventional de facto standard method, in terms of the embedding time and the probability of obtaining a feasible solution.

IEICE Transactions on Information and Systems•Aug 31, 2019•33 citations

Implemented Parallel Annealing in Scalable Fully Coupled Annealing Processing System

Kaoru Yamamoto, T. Kawahara

There has been progress in annealing processors for solving combinatorial optimization problems. There are two types of annealing processors: the "sparsely coupled" type, which implements only some spin-to-spin couplings, and the "fully coupled" type, which implements all spin-to-spin couplings. The latter has the advantage of having a large number of problems to be solved per spin, but had been said to have the disadvantage of poor scalability due to the complicated coupling. To overcome this, we first created a scalable Fully coupled annealing processing system (SFCAPS) by using multi-chip operation and implemented it on an FPGA board. This is to reduce the amount of coupling per chip by performing the multi-chip operation, and to improve the scalability by facilitating the connection between the chips. However, in the architecture, multi-chip operation could not be fully used and most of the chips on the board were idle for a large amount of time. Therefore, for this study, we implemented a parallel annealing method called multi-spin threading on this architecture to reduce the number of idle chips and demonstrated that the architecture can operate more efficiently. As a result, the architecture became more efficient, which raised the parallelism of the architecture. This has resulted in an average 5% improvement in the accuracy of the annealing processor's solution, demonstrating that it is easier to achieve a high accuracy solution.

IEEE World Symposium on Applied Machine Intelligence and Informatics (SAMI)•Mar 2, 2022•4 citations
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.
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.
Combinatorial optimization problems ubiquitously appear in AI applications, e.g. machine learning, operational planning, drug discovery, etc. Yet, their NP-hardness makes them notoriously difficult to solve on present computers. To address this problem, new hardware architectures [1, 4], called annealers, have emerged in recent years. Annealers exploit the fact that combinatorial optimization problems can be mapped to the ground state search of an Ising model, where the combination of N spins (σ- ∈ f-1}. x=1, ...,N) with lowest Ising energy represents the optimal solution to the problem (Fig. 7.3.1).
Autonomous navigation serves as a versatile technology prominently used in logistics and transportation. The application of automatic guided vehicles has become pervasive within the realm of factory automation, as shown in Fig. 30.4.1. For such applications, path planning and collision avoidance are two main tasks. Both tasks are classified as combinatorial optimization problems (COPs), and finding their optimal solutions is time-consuming [1]. A COP can be mapped to an Ising model with spin couplings based on the nature of the problem. Annealing is then applied to find the solution by iteratively updating spins until the states of the spins reach the lowest energy (known as a Hamiltonian). Digital annealers [2] –[4] have been demonstrated to accelerate solving COPs with exponential complexity. Some designs [2] [3] only support small-scale COPs because of the limited number of spins. The other [4] can solve larger problems, while the problem complexity is still limited by their sparse spin connections. Mapping a COP onto an Ising model and vice versa is necessary for solving a specific problem, which is also not addressed in the previous hardware digital annealers.
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.
Combinatorial optimization problems with a large solution space are difficult to solve just using von Neumann computers. Ising machines or annealing machines have been developed to tackle these problems as a promising Non-von Neumann computer. In order to use these annealing machines, every combinatorial optimization problem is mapped onto the physical Ising model, which consists of spins, interactions between them, and their external magnetic fields. Then the annealing machines operate so as to search the ground state of the physical Ising model, which corresponds to the optimal solution of the original combinatorial optimization problem. A combinatorial optimization problem can be firstly described by an ideal fully-connected Ising model but it is very hard to embed it onto the physical Ising model topology of a particular annealing machine, which causes one of the largest issues in annealing machines. In this paper, we propose a fully-connected Ising model embedding method targeting for CMOS annealing machine. The key idea is that the proposed method replicates every logical spin in a fully-connected Ising model and embeds each logical spin onto the physical spins with the same chain length. Experimental results through an actual combinatorial problem show that the proposed method obtains spin embeddings superior to the conventional de facto standard method, in terms of the embedding time and the probability of obtaining a feasible solution.
There has been progress in annealing processors for solving combinatorial optimization problems. There are two types of annealing processors: the "sparsely coupled" type, which implements only some spin-to-spin couplings, and the "fully coupled" type, which implements all spin-to-spin couplings. The latter has the advantage of having a large number of problems to be solved per spin, but had been said to have the disadvantage of poor scalability due to the complicated coupling. To overcome this, we first created a scalable Fully coupled annealing processing system (SFCAPS) by using multi-chip operation and implemented it on an FPGA board. This is to reduce the amount of coupling per chip by performing the multi-chip operation, and to improve the scalability by facilitating the connection between the chips. However, in the architecture, multi-chip operation could not be fully used and most of the chips on the board were idle for a large amount of time. Therefore, for this study, we implemented a parallel annealing method called multi-spin threading on this architecture to reduce the number of idle chips and demonstrated that the architecture can operate more efficiently. As a result, the architecture became more efficient, which raised the parallelism of the architecture. This has resulted in an average 5% improvement in the accuracy of the annealing processor's solution, demonstrating that it is easier to achieve a high accuracy solution.