CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability. The maximum satisfiability (MAX-SAT) problem, especially the weighted version, has extensive applications. Weighted MAX-SAT instances encoded from real-world applications may be very large, which calls for efficient approximate methods, mainly stochastic local search (SLS) ones. However, few works exist on SLS algorithms for weighted MAX-SAT. In this paper, we propose a new heuristic called CCM for weighted MAX-SAT. The CCM heuristic prefers to select a CCMP variable. By combining CCM with random walk, we design a simple SLS algorithm dubbed CCLS for weighted MAX-SAT. The CCLS algorithm is evaluated against a state-of-the-art SLS solver IRoTS and two state-of-the-art complete solvers namely akmaxsat_ls and New WPM2, on a broad range of weighted MAX-SAT instances. Experimental results illustrate that the quality of solution found by CCLS is much better than that found by IRoTS, akmaxsat_ls and New WPM2 on most industrial, crafted and random instances, indicating the efficiency and the robustness of the CCLS algorithm. Furthermore, CCLS is evaluated in the weighted and unweighted MAX-SAT tracks of incomplete solvers in the Eighth Max-SAT Evaluation (Max-SAT 2013), and wins four tracks in this evaluation, illustrating that the performance of CCLS exceeds the current state-of-the-art performance of SLS algorithms on solving MAX-SAT instances.

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

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

  1. Cai, Shaowei; Lei, Zhendong: Old techniques in new ways: clause weighting, unit propagation and hybridization for maximum satisfiability (2020)
  2. 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)
  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. Xu, Zhenxing; He, Kun; Li, Chu-Min: An iterative path-breaking approach with mutation and restart strategies for the MAX-SAT problem (2019)
  6. Lang, Jérôme; Mengin, Jérôme; Xia, Lirong: Voting on multi-issue domains with conditionally lexicographic preferences (2018)
  7. Zhang, Yongfei; Wu, Jun; Zhang, Liming; Zhao, Peng; Zhou, Junping; Yin, Minghao: An efficient heuristic algorithm for solving connected vertex cover problem (2018)
  8. Ansótegui, Carlos; Gabàs, Joel: WPM3: an (in)complete algorithm for weighted partial MaxSAT (2017)
  9. Luo, Chuan; Cai, Shaowei; Su, Kaile; Huang, Wenxuan: CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability (2017)
  10. Berend, Daniel; Twitto, Yochai: The normalized autocorrelation length of random MAX (r)-SAT converges in probability to ((1-1/2^r)/r) (2016)
  11. Cai, Shaowei; Luo, Chuan; Lin, Jinkun; Su, Kaile: New local search methods for partial MaxSAT (2016)
  12. Liu, Yan-Li; Li, Chu-Min; He, Kun; Fan, Yi: Breaking cycle structure to improve lower bound for Max-SAT (2016)
  13. Luo, Chuan; Cai, Shaowei; Wu, Wei; Jie, Zhong; Su, Kaile: CCLS: an efficient local search algorithm for weighted maximum satisfiability (2015)
  14. Mangal, Ravi; Zhang, Xin; Nori, Aditya V.; Naik, Mayur: Volt: a lazy grounding framework for solving very large maxsat instances (2015)