A continuous-time MaxSAT solver with high analog performance.
A continuous-time MaxSAT solver with high analog performance.
复制标题
DOI：
10.1038/s41467-018-07327-2
复制
发表时间：
2018-11-19
影响因子：
16.6
通讯作者：
Ercsey-Ravasz M
中科院分区：
文献类型：
--
作者：
Molnár B;Molnár F;Varga M;Toroczkai Z;Ercsey-Ravasz M
许多现实生活中的优化问题可以用布尔逻辑表示为 MaxSAT，一类问题的任务是找到满足最大逻辑约束数量的变量的布尔赋值。由于 MaxSAT 是 NP 难问题，因此目前还没有已知的算法可以有效地解决这些问题。在这里，我们提出了 MaxSAT 的连续时间模拟求解器，并表明逃逸率的缩放（求解器动态的不变量）可以预测可满足约束的最大数量，通常早于找到最佳分配。通过模拟求解器，我们说明了其在 MaxSAT 竞争问题上的性能，然后将其应用于双色 Ramsey 数 R(m, m) 问题。虽然它在 N ≤ 42 个顶点上找到了没有完整图的单色 5 团的着色，但 N = 43 的最佳着色有两个单色 5 团，支持 R(5, 5) = 43 的猜想。这种方法显示了连续时间模拟动力系统作为离散优化算法的潜力。在处理某些类别的问题时，连续时间计算范式可以代表标准数字计算范式的一种可行替代方案。在这里，作者提出了连续时间求解器的通用版本，并模拟了其在解决 MaxSAT 和双色 Ramsey 问题中的性能。
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. Continuous-time computation paradigm could represent a viable alternative to the standard digital one when dealing with certain classes of problems. Here, the authors propose a generalised version of a continuous-time solver and simulate its performances in solving MaxSAT and two-colour Ramsey problems.
登录
查看更多内容
影响因子：
4.6
作者：
Ercsey-Ravasz, Maria;Toroczkai, Zoltan
通讯作者：
Toroczkai, Zoltan
DOI：
10.1007/978-3-540-24605-3_37
发表时间：
2004-01-01
期刊：
THEORY AND APPLICATIONS OF SATISFIABILITY TESTING
影响因子：
--
作者：
Eén, N;Sörensson, N
通讯作者：
Sörensson, N
DOI：
10.1088/0305-4470/15/10/028
发表时间：
1982-01-01
期刊：
JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL
影响因子：
--
作者：
BARAHONA, F
通讯作者：
BARAHONA, F
影响因子：
7.2
作者：
Ahmad, Siti Halimah;Jamil, Siti Munira;Ismail, Ahmad Fauzi
通讯作者：
Ismail, Ahmad Fauzi
影响因子：
3.5
作者：
FRAENKEL, AS
通讯作者：
FRAENKEL, AS