New Multi-Policy-Based Annealer for Solving Real-World Combinatorial Optimization Problems

A fully-connected annealer extendable to a multi-chip system and featuring a multi-policy mechanism has been designed by Tokyo Tech researchers to solve a broad class of combinatorial optimization (CO) problems relevant to real-world scenarios quickly and efficiently. Named Amorphica, the annealer has the ability to fine-tune parameters according to a specific target CO problem and has potential applications in logistics, finance, machine learning, and so on.

The modern world has grown accustomed to an efficient delivery of goods right at our doorsteps. But did you know that realizing such an efficiency requires solving a mathematical problem, namely what is the best possible route between all the destinations? Known as the "travelling salesman problem," this belongs to a class of mathematical problems known as "combinatorial optimization" (CO) problems.

As the number of destinations increases, the number of possible routes grows exponentially, and a brute force method based on exhaustive search for the best route becomes impractical. Instead, an approach called "annealing computation" is adopted to find the best route quickly without an exhaustive search. Yet, a numerical study done by Tokyo Tech researchers has shown that while there exists many annealing computation methods, there is no one method suitable for solving a broad class of CO problems. Therefore, there is a need for an annealing mechanism that features multiple annealing methods (a multi-policy mechanism) to target a variety of such problems.

Fortunately, the same team of researchers, led by Assistant Professor Kazushi Kawamura and Professor Masato Motomura from Tokyo Institute of Technology (Tokyo Tech), have reported a new annealer that features such a multi-policy approach or "metamorphic annealing." Their findings are published in the Proceeding of ISSCC2023 and will be presented in the upcoming 2023 International Solid-State Circuits Conference.

"In the annealing computation, a CO problem is represented as an energy function in terms of (pseudo) spin vectors. We start from an initially randomized spin vector configuration and then update it stochastically to find the minimum energy states by reducing its (pseudo) temperature. This closely mirrors the annealing process of metals where hot metals are cooled down in a controlled manner," explains Dr. Kawamura. "Our annealer named Amorphica features multiple annealing methods, including a new one proposed by our team. This provides it the ability to adopt the annealing method to the specific CO problem at hand."

The team designed Amorphica to address the limitations of previous annealers, namely that their applicability is limited to only a few CO problems. This is firstly due to the fact that these annealers are local-connection ones, meaning they can only deal with spin models having local inter-spin coupling. Another reason is that they do not have flexibility in terms of annealing methods and parameter control. These issues were solved in Amorphica by employing a full-connection spin model and incorporating finely controllable annealing methods and parameters. In addition, the team introduced a new annealing policy called "ratio-controlled parallel annealing" to improve the convergence speed and stability of existing annealing methods.

Additionally, Amorphica can be extended to a multi-chip, full-connection system with reduced inter-chip data transfer. On testing Amorphica against a GPU, the researchers found that it was up to 58 times faster while using only (1/500) power consumption, meaning it achieves around 30k times more energy efficient.

"With a full-connection annealer like Amorphica, we can now deal with arbitrary topologies and densities of inter-spin couplings, even when they are irregular. This, in turn, would allow us to solve real-world CO problems such as those related to logistics, finance, and machine learning," concludes Prof. Motomura.

• Reference

Authors :	Kazushi Kawamura1, Jaehoon Yu1, Daiki Okonogi1, Satoru Jimbo1, Genta Inoue1, Akira Hyodo1, Ángel López García-Arias1, Kota Ando2, Bruno Hideki Fukushima-Kimura2, Ryota Yasudo3, Thiem Van Chu1, Masato Motomura1
Title :	Amorphica: 4-Replica 512 Fully Connected Spin 336MHz Metamorphic Annealer with Programmable Optimization Strategy and Compressed-Spin-Transfer Multi-Chip Extension
Journal :	Proceeding of ISSCC2023
Affiliations :	1Tokyo Institute of Technology 2Hokkaido University 3Kyoto University
* Corresponding author's email: kawamura@artic.iir.titech.ac.jp