Applying aspiration in local search for satisfiability

Cong Peng, Zhongwei Xu and Meng Mei

PLOS ONE, 2020, vol. 15, issue 4, 1-16

Abstract: The Boolean Satisfiability problem (SAT) is a prototypical NP-complete problem, which has been widely studied due to its significant importance in both theory and applications. Stochastic local search (SLS) algorithms are among the most efficient approximate methods available for solving certain types of SAT instances. The quantitative configuration checking (QCC) heuristic is an effective approach for improving SLS algorithms on solving the SAT problem, resulting in an efficient SLS solver for SAT named Swqcc. In this paper, we focus on combining the QCC heuristic with an aspiration mechanism, and then design a new heuristic called QCCA. On the top of Swqcc, we utilize the QCCA heuristic to develop a new SLS solver dubbed AspiSAT. Through extensive experiments, the results illustrate that, on random 3-SAT instances, the performance of AspiSAT is much better than that of Swqcc and Sparrow, which is an influential and efficient SLS solver for SAT. In addition, we further enhance the original clause weighting schemes employed in Swqcc and AspiSAT, and thus obtain two new SLS solvers called Ptwqcc and AspiPT, respectively. The eperimental results present that both Ptwqcc and AspiPT outperform Swqcc and AspiSAT on random 5-SAT instances, indicating that both QCC and QCCA heuristics are able to cooperate effectively with different clause weighting schemes.

Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0231702 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 31702&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0231702

DOI: 10.1371/journal.pone.0231702

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().