Improving Two-Mode Algorithm via Probabilistic Selection for Solving Satisfiability Problem

Huimin Fu, Shaowei Cai, Guanfeng Wu, J. Liu, Xin Yang, Yang Xu

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Article number119751
Pages (from-to)1-21
Number of pages21
JournalInformation Sciences
Volume653
Issue number119751
Early online date6 Oct 2023
DOIs
Publication statusPublished (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

Fingerprint

Dive into the research topics of 'Improving Two-Mode Algorithm via Probabilistic Selection for Solving Satisfiability Problem'. Together they form a unique fingerprint.

Cite this