将伊辛问题转化为平滑函数，用梯度法高效求解局部最优。
Local-Minima-Preserving Continuous Relaxation of Ising Problems
- 构建多项式松弛，保持原问题单翻转局部极小点对应关系。
- 在自旋玻璃、最大割和数划分等难题上表现优异。
- 适合需要快速求解组合优化的科研与工程场景。
广义伊辛问题涵盖最大割（MAX-CUT）、数划分（NPP）和最大独立集等多种难解组合优化问题。本文研究该问题的单翻转局部极小点，提出一种多项式松弛，并证明了景观等价定理：松弛后的局部极小点与原问题的单翻转局部极小点一一对应。这一保证使伊辛问题转化为寻找平滑函数的局部极小点，从而可使用ADAM等基于梯度的优化器。实验表明，该方法具有良好的可扩展性，在自旋玻璃模型、MAX-CUT和NPP等挑战性基准上均取得强性能。
原文摘要 · Abstract (English)
The generalized Ising problem captures a broad spectrum of hard combinatorial problems, including MAX-CUT, Number Partitioning (NPP), and Maximum Independent Set. In this work, we consider the notion of one-flip local minima for this problem. We construct a polynomial relaxation and prove the landscape equivalence theorem: there exists a one-to-one correspondence between the local minima of the relaxation and the one-flip minima of the original Ising problem. This guarantee reduces the Ising problem to finding the local minima of a smooth function, allowing us to leverage gradient-based optimizers such as ADAM. We demonstrate that our method is scalable and it achieves strong performance across challenging benchmarks, including spin-glass models, MAX-CUT, and NPP.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。