Faculty of Physics, Babeş-Bolyai University, Cluj-Napoca, 400084, Romania.
Faculty of Mathematics and Computer Science, Babeş-Bolyai University, Cluj-Napoca, 400084, Romania.
Nat Commun. 2018 Nov 19;9(1):4864. doi: 10.1038/s41467-018-07327-2.
Many real-life optimization problems can be formulated in Boolean logic as MaxSAT, a class of problems where the task is finding Boolean assignments to variables satisfying the maximum number of logical constraints. Since MaxSAT is NP-hard, no algorithm is known to efficiently solve these problems. Here we present a continuous-time analog solver for MaxSAT and show that the scaling of the escape rate, an invariant of the solver's dynamics, can predict the maximum number of satisfiable constraints, often well before finding the optimal assignment. Simulating the solver, we illustrate its performance on MaxSAT competition problems, then apply it to two-color Ramsey number R(m, m) problems. Although it finds colorings without monochromatic 5-cliques of complete graphs on N ≤ 42 vertices, the best coloring for N = 43 has two monochromatic 5-cliques, supporting the conjecture that R(5, 5) = 43. This approach shows the potential of continuous-time analog dynamical systems as algorithms for discrete optimization.
许多现实生活中的优化问题可以用布尔逻辑表示为 MaxSAT，这是一类问题，任务是找到满足最大数量逻辑约束的变量的布尔赋值。由于 MaxSAT 是 NP 难问题，因此没有已知的算法可以有效地解决这些问题。在这里，我们提出了一种用于 MaxSAT 的连续时间模拟求解器，并表明求解器动力学的逃逸率的标度可以预测满足的最大数量的约束，通常在找到最佳赋值之前就可以很好地预测。通过模拟求解器，我们说明了它在 MaxSAT 竞赛问题上的性能，然后将其应用于双色 Ramsey 数 R(m, m)问题。尽管它在 N≤42 个顶点的图上没有找到具有完全图的单色 5-团的着色，但对于 N=43 的最佳着色有两个单色 5-团，这支持了 Ramsey 数猜想 R(5, 5)=43。这种方法展示了连续时间模拟动力系统作为离散优化算法的潜力。
