Machine Learning Methods in Solving the Boolean Satisfiability Problem
文献类型:期刊论文
作者 | Wenxuan Guo2; Hui-Ling Zhen1; Xijun Li1; Wanqian Luo1; Mingxuan Yuan1; Yaohui Jin2; Junchi Yan2 |
刊名 | 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/56000] ![]() |
专题 | 自动化研究所_学术期刊_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,Hui-Ling Zhen,Xijun Li,et al. Machine Learning Methods in Solving the Boolean Satisfiability Problem[J]. Machine Intelligence Research,2023,20(5):640-655. |
APA | Wenxuan Guo.,Hui-Ling Zhen.,Xijun Li.,Wanqian Luo.,Mingxuan Yuan.,...&Junchi Yan.(2023).Machine Learning Methods in Solving the Boolean Satisfiability Problem.Machine Intelligence Research,20(5),640-655. |
MLA | Wenxuan Guo,et al."Machine Learning Methods in Solving the Boolean Satisfiability Problem".Machine Intelligence Research 20.5(2023):640-655. |
入库方式: OAI收割
来源:自动化研究所
其他版本
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。