Improving performance of CDCL SAT solvers by automated design of variable selection heuristics
Improving performance of CDCL SAT solvers by automated design of variable selection heuristics
复制标题
通过变量选择启发式的自动设计提高 CDCL SAT 求解器的性能
DOI：
10.1109/ssci.2017.8280953
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
W. Siever
中科院分区：
文献类型：
--
作者：
Marketa Illetskova;Alex R. Bertels;J. M. Tuggle;A. Harter;Samuel N. Richter;D. Tauritz;S. Mulder;Denis Bueno;Michelle Leger;W. Siever
许多现实世界的工程和科学问题都可以映射到布尔可满足性问题（SAT）。 CDCL SAT求解器是最有效的求解器之一。先前的工作表明，源自特定问题类别的实例表现出独特的基础结构，从而影响求解器可变选择方案的有效性。因此，将求解器的变量评分启发式定制为特定问题类别可以显着提高求解器的性能；但是，手动执行这种定制是非常密集的。本文介绍了一个系统，用于自动化CDCL求解器的可变评分启发式方法的设计，从而使求解器适合任意问题类别。提供了实验结果，证明了该系统使用遗传编程的异步平行超高术方法进化可变评分的启发式方法，具有为特定问题类别创建更有效的求解器的潜力。
Many real-world engineering and science problems can be mapped to Boolean satisfiability problems (SAT). CDCL SAT solvers are among the most efficient solvers. Previous work showed that instances derived from a particular problem class exhibit a unique underlying structure which impacts the effectiveness of a solver's variable selection scheme. Thus, customizing the variable scoring heuristic of a solver to a particular problem class can significantly enhance the solver's performance; however, manually performing such customization is very labor intensive. This paper presents a system for automating the design of variable scoring heuristics for CDCL solvers, making it feasible to tailor solvers to arbitrary problem classes. Experimental results are provided demonstrating that this system, which evolves variable scoring heuristics using an asynchronous parallel hyper-heuristics approach employing genetic programming, has the potential to create more efficient solvers for particular problem classes.
影响因子：
14.4
作者：
Hutter, Frank;Xu, Lin;Leyton-Brown, Kevin
通讯作者：
Leyton-Brown, Kevin
影响因子：
3.6
作者：
Burke, Edmund K.;Gendreau, Michel;Qu, Rong
通讯作者：
Qu, Rong