Backing Backtracking
Möhle S., Biere A. (2019) Backing Backtracking. In: Janota M., Lynce I. (eds) Theory and Applications of Satisfiability Testing – SAT 2019. SAT 2019. Lecture Notes in Computer Science, vol 11628. Springer, Cham. https://doi.org/10.1007/978-3-030-24258-9_18
Abstract
Non-chronological backtracking was considered an important and necessary feature of conflict-driven clause learning (CDCL).译文:非按时间顺序回溯被认为是冲突驱动小句学习(CDCL)的一个重要且必要的特征。 However, a SAT solver combining CDCL with chronological backtracking succeeded in the main track of the SAT Competition 2018.译文:然而,将CDCL与时间回溯相结合的SAT求解器在2018年SAT竞赛的主赛道上获得了成功。 In that solver, multiple invariants considered crucial for CDCL were violated.译文:在那个求解器中,多个被认为对CDCL至关重要的不变量被调整了。 In particular, decision levels of literals on the trail were not necessarily increasing anymore. 译文:特别是,在测试过程中,文本的决策级别不再必然增加。 The corresponding paper presented at SAT 2018 described the algorithm and provided empirical evidence of its correctness, but a formalization and proofs were missing. 译文:在SAT 2018上发表的相应论文描述了该算法,并提供了其正确性的经验证据,但缺少形式化和证明。 Our contribution is to fill this gap. We further generalize the approach, discuss implementation details, and empirically confirm its effectiveness in an independent implementation.译文:我们的贡献就是填补这一空白。我们进一步推广了该方法,讨论了实现细节,并在独立实现中实证验证了其有效性。 |
|