论文标题
Nlocalsat：通过解决方案预测来增强本地搜索
NLocalSAT: Boosting Local Search with Solution Prediction
论文作者
论文摘要
布尔可满足性问题（SAT）是计算机科学中著名的NP完整问题。解决令人满意的SAT问题的有效方法是随机局部搜索（SLS）。但是，在这种方法中，初始化是随机分配的，这会影响SLS求解器的有效性。为了解决这个问题，我们提出了nlocalsat。 Nlocalsat将SLS与解决方案预测模型相结合，该模型通过使用神经网络更改初始化分配来增强SLS。我们在五个SLS求解器（CCANR，SPARROW，CPSPARROW，YALSAT和PROBSAT）上评估了Nlocalsat，并在随机的SAT竞争2018中随机实例。实验结果表明，NloCalsat的求解器可在原始SLS溶液中提高27％〜62％。
The Boolean satisfiability problem (SAT) is a famous NP-complete problem in computer science. An effective way for solving a satisfiable SAT problem is the stochastic local search (SLS). However, in this method, the initialization is assigned in a random manner, which impacts the effectiveness of SLS solvers. To address this problem, we propose NLocalSAT. NLocalSAT combines SLS with a solution prediction model, which boosts SLS by changing initialization assignments with a neural network. We evaluated NLocalSAT on five SLS solvers (CCAnr, Sparrow, CPSparrow, YalSAT, and probSAT) with instances in the random track of SAT Competition 2018. The experimental results show that solvers with NLocalSAT achieve 27% ~ 62% improvement over the original SLS solvers.
