Abstract
The satisfiability problem (SAT) is a critically important issue in multiple branches of computer science and artificial intelligence, with its relevance in industrial applications being of particular Significance CCAnr is the current leading stochastic local search (SLS) solver for tackling crafted satisfiable instances. It uses a two-mode strategy, greedy mode and diversification mode. In the present work, we employ a probabilistic selection approach to enhance CCAnr, leading to a new algorithm called ProbCCAnr. Experiments are carried out using the random SAT benchmarks and structured SAT benchmarks including instances encoded from mathematical problems and application problems. The experiments demonstrate that ProbCCAnr significantly improves the performance of state-of-the-art SLS algorithms including CCAnr and ProbSAT, among others. Moreover, ProbCCAnr shows better performance than state of the art complete solvers.
Original language | English |
---|---|
Article number | 119751 |
Pages (from-to) | 1-21 |
Number of pages | 21 |
Journal | Information Sciences |
Volume | 653 |
Issue number | 119751 |
Early online date | 6 Oct 2023 |
DOIs | |
Publication status | Published (in print/issue) - 1 Jan 2024 |
Bibliographical note
This work was supported by the National Natural Science Foundation of China (No. 62206227, 61976130), the Natural Science Foundation of Sichuan (No. 2022NSFSC0464), and the China Scholarship Council.Funding Information:
This work was supported by the National Natural Science Foundation of China (No. 62206227, 61976130), the Natural Science Foundation of Sichuan (No. 2022NSFSC0464), and the China Scholarship Council.
Publisher Copyright:
© 2023
Keywords
- Stochastic local search
- Satisfiability
- Two-mode solver
- Structured problems