Machine Learning Methods in Solving the Boolean Satisfiability Problem  

作　　者：Wenxuan Guo Hui-Ling Zhen Xijun Li Wanqian Luo Mingxuan Yuan Yaohui Jin Junchi Yan 

机构地区：[1]MoE Key Laboratory of Artificial Intelligence,Shanghai Jiao Tong University,Shanghai 200240,China [2]Noah′s Ark Laboratory,Huawei Ltd.,Shenzhen 518129,China

出　　处：《Machine Intelligence Research》2023年第5期640-655,共16页机器智能研究（英文版）

基　　金：supported by National Key Research and Development Program of China(No.2020AAA0107600);National Science Foundation of China(No.62102258);Shanghai Pujiang Program,China(No.21PJ1407300);Shanghai Municipal Science and Technology Major Project,China(No.2021SHZDZX0102);Science and Technology Commission of Shanghai Municipality Project,China(No.22511105100),and also sponsored by Huawei Ltd,China.

摘　　要：This paper reviews the recent literature on solving the Boolean satisfiability problem(SAT),an archetypal N P-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 ML SAT 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/ThinklabSJTU/awesome-ml4co.Keywords:Machine learning(ML),Boolean satisfiability(SAT),deep learning,graph neural networks(GNNs),combinatorial optimization.

关 键 词：Machine learning(ML) Boolean satisfiability(SAT) deep learning graph neural networks(GNNs) combinatorial optimization 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程] TP391.41[自动化与计算机技术—控制科学与工程] R318[医药卫生—生物医学工程]