Local search for Boolean satisfiability with configuration checking and subscore. This paper presents and analyzes two new efficient local search strategies for the Boolean Satisfiability (SAT) problem. We start by proposing a local search strategy called configuration checking (CC) for SAT. The CC strategy results in a simple local search algorithm for SAT called Swcc, which shows promising experimental results on random 3-SAT instances, and outperforms TNM, the winner of SAT Competition 2009. par However, the CC strategy for SAT is still in a nascent stage, and Swcc cannot yet compete with Sparrow2011, which won SAT Competition 2011 just after Swcc had been designed. The CC strategy seems too strict in that it forbids flipping those variables even with great scores, if they do not satisfy the CC criterion. We improve the CC strategy by adopting an aspiration mechanism, and get a new variable selection heuristic called configuration checking with aspiration (CCA). The CCA heuristic leads to an improved algorithm called Swcca, which exhibits state-of-the-art performance on random 3-SAT instances and crafted ones. par The third contribution concerns improving local search algorithms for random $ k$-SAT instances with $k>3$. Although the SAT community has made great achievements in solving random 3-SAT instances, the progress lags far behind on random $k$-SAT instances with $k>3$. This work proposes a new variable property called subscore, which is utilized to break ties in the CCA heuristic when candidate variables for flipping have the same score. The resulting algorithm CCAsubscore is very efficient for solving random $ k$-SAT instances with $k>3$, and significantly outperforms other state-of-the-art ones. Combining Swcca and CCAsubscore, we obtain a local search SAT solver called CCASat, which was ranked first in the random track of SAT Challenge 2012. par Additionally, we perform theoretical analyses on the CC strategy and the subscore property, and show interesting results on these two heuristics. Particularly, our analysis indicates that the CC strategy is more effective for $ k$-SAT with smaller $ k$, while the subscore notion is not suitable for solving random 3-SAT.

References in zbMATH (referenced in 12 articles , 1 standard article )

Showing results 1 to 12 of 12.
Sorted by year (citations)

  1. Chu, Yi; Liu, Boxiao; Cai, Shaowei; Luo, Chuan; You, Haihang: An efficient local search algorithm for solving maximum edge weight clique problem in large graphs (2020)
  2. Li, Ruizhi; Wang, Yupan; Hu, Shuli; Jiang, Jianhua; Ouyang, Dantong; Yin, Minghao: Solving the set packing problem via a maximum weighted independent set heuristic (2020)
  3. Wang, Yiyuan; Cai, Shaowei; Chen, Jiejiang; Yin, Minghao: SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem (2020)
  4. Wu, Jun; Li, Chu-Min; Jiang, Lu; Zhou, Junping; Yin, Minghao: Local search for diversified top-(k) clique search problem (2020)
  5. Yamashita, Hiroshi; Aihara, Kazuyuki; Suzuki, Hideyuki: Timescales of Boolean satisfiability solver using continuous-time dynamical system (2020)
  6. Xu, Zhenxing; He, Kun; Li, Chu-Min: An iterative path-breaking approach with mutation and restart strategies for the MAX-SAT problem (2019)
  7. Abramé, André; Habet, Djamal; Toumi, Donia: Improving configuration checking for satisfiable random (k)-SAT instances (2017)
  8. Luo, Chuan; Cai, Shaowei; Su, Kaile; Huang, Wenxuan: CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability (2017)
  9. Cai, Shaowei; Luo, Chuan; Lin, Jinkun; Su, Kaile: New local search methods for partial MaxSAT (2016)
  10. Li, Ruizhi; Hu, Shuli; Zhang, Haochen; Yin, Minghao: An efficient local search framework for the minimum weighted vertex cover problem (2016)
  11. Cai, Shaowei; Luo, Chuan; Su, Kaile: CCAnr: a configuration checking based local search solver for non-random satisfiability (2015)
  12. Cai, Shaowei; Su, Kaile: Local search for Boolean satisfiability with configuration checking and subscore (2013)