Dynamical System-Based Computational Models for Solving Combinatorial Optimization on Hypergraphs
Dynamical System-Based Computational Models for Solving Combinatorial Optimization on Hypergraphs
复制标题
DOI：
10.1109/jxcdc.2023.3235113
复制
发表时间：
2023-06-01
影响因子：
2.4
通讯作者：
Shukla, Nikhil
中科院分区：
文献类型：
--
作者：
Bashar, Mohammad Khairul;Mallick, Antik;Shukla, Nikhil
动力系统的内禀能量最小化为组合优化中的计算难题的目标函数最小化提供了一个有价值的工具。然而，大多数先前的工作集中于将这样的动态映射到目标函数具有二次度的组合优化问题[例如，最大切割（MaxCut）];这样的问题可以使用图来表示和分析。然而，开发这种模型的问题，需要的目标函数的程度大于2，随后，需要使用超图数据结构的工作，是相对稀疏的。在这项工作中，我们开发了动力系统启发的计算模型的几个这样的问题。具体来说，我们定义了“能量函数”的超图为基础的组合问题，范围从布尔可满足性（SAT）及其变种，以整数分解，随后，定义所产生的系统动力学。我们还表明，设计方法是适用于优化问题的二次度，并使用它来开发一个新的动力系统制定最小化伊辛哈密顿量。我们的工作不仅扩大了可以直接映射到并使用物理模型解决的问题的范围，而且还为设计用于解决组合优化的高性能加速器创造了新的机会。
The intrinsic energy minimization in dynamical systems offers a valuable tool for minimizing the objective functions of computationally challenging problems in combinatorial optimization. However, most prior works have focused on mapping such dynamics to combinatorial optimization problems whose objective functions have quadratic degree [e.g., maximum cut (MaxCut)]; such problems can be represented and analyzed using graphs. However, the work on developing such models for problems that need objective functions with degree greater than two, and subsequently, entail the use of hypergraph data structures, is relatively sparse. In this work, we develop dynamical system-inspired computational models for several such problems. Specifically, we define the "energy function" for hypergraph-based combinatorial problems ranging from Boolean Satisfiability (SAT) and its variants to integer factorization, and subsequently, define the resulting system dynamics. We also show that the design approach is applicable to optimization problems with quadratic degree, and use it to develop a new dynamical system formulation for minimizing the Ising Hamiltonian. Our work not only expands on the scope of problems that can be directly mapped to, and solved using physics-inspired models, but also creates new opportunities to design high-performance accelerators for solving combinatorial optimization.