Machine Learning Methods in Solving the Boolean Satisfiability Problem

• DOI: 10.1007/s11633-022-1396-2
• Publication Date: 2023-06-01T05:01:50Z
• Authors: Wenxuan Guo; Hui-Ling Zhen; Xijun Li; Wanqian Luo; Mingxuan Yuan; Yaohui Jin; Junchi Yan
• Keywords: Boolean satisfiability problem; Satisfiability

This paper reviews the recent literature on solving Boolean satisfiability problem (SAT), an archetypal $$\cal{N}\cal{P}$$ -complete problem, with aid of machine learning (ML) techniques. Over last decade, society advances rapidly and surpasses human performance several tasks. trend also inspires a number works that apply methods for SAT solving. In this survey, we examine evolving ML solvers from naive classifiers handcrafted features to emerging end-to-end solvers, as well progress combinations existing conflict-driven clause (CDCL) local search methods. Overall, is promising yet challenging research topic. We conclude limitations current suggest possible future directions. The collected list available at https://github.com/Thinklab-SJTU/awesome-ml4co .