中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
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
DOI10.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收割

来源:自动化研究所

浏览0
下载0
收藏0
其他版本

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。