Computational Models Based on Synchronized Oscillators for Solving Combinatorial Optimization Problems
Computational Models Based on Synchronized Oscillators for Solving Combinatorial Optimization Problems
复制标题
DOI：
10.1103/physrevapplied.17.064064
复制
发表时间：
2022-06-30
影响因子：
4.6
通讯作者：
Shukla, Nikhil
中科院分区：
文献类型：
--
作者：
Mallick, Antik;Bashar, Mohammad Khairul;Shukla, Nikhil
动态系统中能量的自然最小化与组合优化问题中目标函数的最小化之间的等价性为设计此类问题的动态系统启发的计算模型和求解器提供了一种很有前途的方法。例如，耦合电子振荡器在二次谐波注入下的基态能量可以直接映射到最大切割问题的最优解。然而，先前的工作集中在这类问题的有限集合上。因此，在这项工作中，我们为从Max-K-Cut（最大切割问题的一般版本）到旅行推销员问题的广泛组合优化问题制定了基于同步振荡器动力学的计算模型。我们表明，通过适当设计耦合函数和外部注入振荡器，可以设计同步振荡器动力学来解决这些不同的组合优化问题。我们的工作标志着朝着扩展基于振荡器的模拟加速器的功能迈出了一步，并进一步扩展了组合优化问题的动态系统求解器的范围。
The equivalence between the natural minimization of energy in a dynamic system and the minimization of an objective function characterizing a combinatorial optimization problem offers a promising approach to design dynamic-system-inspired computational models and solvers for such problems. For instance, the ground-state energy of coupled electronic oscillators, under second-harmonic injection, can be directly mapped to the optimal solution of the maximum-cut problem. However, prior work has focused on a limited set of such problems. Therefore, in this work, we formulate computing models based on synchronized oscillator dynamics for a broad spectrum of combinatorial optimization problems ranging from the Max-K-Cut (the general version of the maximum-cut problem) to the traveling-salesman problem. We show that synchronized oscillator dynamics can be engineered to solve these different combinatorial optimization problems by appropriately designing the coupling function and external injection to the oscillators. Our work marks a step forward towards expanding the functionalities of oscillator-based analog accelerators and furthers the scope of dynamic system solvers for combinatorial optimization problems.