A Parallel-Trial Double-Update Annealing Processor for Enabling Highly-Effective Solution Search of Constrained Combinatorial Optimization Problems

Annealing processors have attracted attention as domain-specific computers to solve combinatorial optimization problems (COPs) efficiently. Their search performance can be further enhanced by the merge method that provides a capability of updating multiple variables simultaneously. However, directly implementing the merge method on annealing processors requires large-scale computational and memory resources. This paper proposes a parallel-trial double-update annealing (PDA) algorithm that efficiently integrates the merge method into the annealing computation flow. Additionally, a PDA processor is implemented on an FPGA by extending the existing near-memory architecture for annealing computation. Experimental results for several COPs demonstrate that the proposed PDA processor achieves superior solution search performance compared to a conventional annealing processor and GPU-based annealing computation.