Machine Learning Methods in Solving the Boolean Satisfiability Problem

doi:10.1007/s11633-022-1396-2

CORC > 自动化研究所 > 中国科学院自动化研究所 > 学术期刊 > International Journal of Automation and Computing

	Machine Learning Methods in Solving the Boolean Satisfiability Problem
	Wenxuan Guo 2
刊名	Machine Intelligence Research
	2023
卷号	20 期号:5 页码:640-655
关键词	Machine learning (ML), Boolean satisfiability (SAT), deep learning, graph neural networks (GNNs), combinatorial optimization
ISSN号	2731-538X
DOI	10.1007/s11633-022-1396-2
英文摘要	This paper reviews the recent literature on solving the Boolean satisfiability problem (SAT), an archetypal NP-complete problem, with the aid of machine learning (ML) techniques. Over the last decade, the machine learning society advances rapidly and surpasses human performance on several tasks. This trend also inspires a number of works that apply machine learning methods for SAT solving. In this survey, we examine the evolving MLSAT solvers from naive classifiers with handcrafted features to emerging end-to-end SAT solvers, as well as recent progress on combinations of existing conflict-driven clause learning (CDCL) and local search solvers with machine learning methods. Overall, solving SAT with machine learning is a promising yet challenging research topic. We conclude the limitations of current works and suggest possible future directions. The collected paper list is available at https://github.com/Thinklab SJTU/awesome-ml4co.
内容类型	期刊论文
源URL	[http://ir.ia.ac.cn/handle/173211/52441]
专题	自动化研究所_学术期刊_International Journal of Automation and Computing
作者单位	1.Noah's Ark Laboratory, Huawei Ltd., Shenzhen 518129, China 2.MoE Key Laboratory of Artificial Intelligence, Shanghai Jiao Tong University, Shanghai 200240, China
推荐引用方式 GB/T 7714	Wenxuan Guo. Machine Learning Methods in Solving the Boolean Satisfiability Problem[J]. Machine Intelligence Research,2023,20(5):640-655.
APA	Wenxuan Guo.(2023).Machine Learning Methods in Solving the Boolean Satisfiability Problem.Machine Intelligence Research,20(5),640-655.
MLA	Wenxuan Guo."Machine Learning Methods in Solving the Boolean Satisfiability Problem".Machine Intelligence Research 20.5(2023):640-655.