Nam Le

Boolean Satisfiability (SAT)

Nam Le
Table of Contents

Boolean Satisfiability (SAT) #

Boolean Satisfiability is a fundamental problem in computer science with applications to formal verification and automated reasoning. Machine learning approaches are increasingly being applied to improve SAT solver heuristics.

Recent Literature #

  1. Graph neural networks and boolean satisfiability. Arxiv, 2017. paper

    Bünz, Benedikt, and Matthew Lamm.

  2. Learning a SAT solver from single-bit supervision. Arxiv, 2018. paper, code

    Selsam, Daniel, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill.

  3. Machine learning-based restart policy for CDCL SAT solvers. SAT, 2018. paper

    Liang, Jia Hui, Chanseok Oh, Minu Mathew, Ciza Thomas, Chunxiao Li, and Vijay Ganesh.

  4. Learning to solve circuit-SAT: An unsupervised differentiable approach. ICLR, 2019. paper, code

    Amizadeh, Saeed, Sergiy Matusevych, and Markus Weimer.

  5. Learning Local Search Heuristics for Boolean Satisfiability. NeurIPS, 2019. paper, code

    Yolcu, Emre and Poczos, Barnabas

  6. Improving SAT solver heuristics with graph networks and reinforcement learning. Arxiv, 2019. paper

    Kurin, Vitaly, Saad Godil, Shimon Whiteson, and Bryan Catanzaro.

  7. Graph neural reasoning may fail in certifying boolean unsatisfiability. Arxiv, 2019. paper

    Chen, Ziliang, and Zhanfu Yang.

  8. Guiding high-performance SAT solvers with unsat-core predictions. SAT, 2019. paper

    Selsam, Daniel, and Nikolaj Bjørner.

  9. G2SAT: Learning to Generate SAT Formulas. NeurIPS, 2019. paper, code

    You, Jiaxuan, Haoze Wu, Clark Barrett, Raghuram Ramanujan, and Jure Leskovec.

  10. Learning Heuristics for Quantified Boolean Formulas through Reinforcement Learning. Arxiv, 2019. paper, code

    Lederman, Gil, Markus N. Rabe, Edward A. Lee, and Sanjit A. Seshia.

  11. Enhancing SAT solvers with glue variable predictions. Arxiv, 2020. paper

    Han, Jesse Michael.

  12. Can Q-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver? NeurIPS, 2020. paper

    Whiteson, Shimon.

  13. Online Bayesian Moment Matching based SAT Solver Heuristics. ICML, 2020. paper, code

    Duan, Haonan, Saeed Nejati, George Trimponias, Pascal Poupart, and Vijay Ganesh.

  14. Learning Clause Deletion Heuristics with Reinforcement Learning. AITP, 2020. paper

    Vaezipoor, Pashootan, Gil Lederman, Yuhuai Wu, Roger Grosse, and Fahiem Bacchus.

  15. Classification of SAT problem instances by machine learning methods. CEUR, 2020. paper

    Danisovszky, Márk, Zijian Győző Yang, and Gábor Kusper.

  16. Predicting Propositional Satisfiability via End-to-End Learning. AAAI, 2020. paper

    Cameron, Chris, Rex Chen, Jason Hartford, and Kevin Leyton-Brown.

  17. Neural heuristics for SAT solving. Arxiv, 2020. paper

    Jaszczur, Sebastian, Michał Łuszczyk, and Henryk Michalewski.

  18. NLocalSAT: Boosting Local Search with Solution Prediction. Arxiv, 2020. paper, code

    Zhang, Wenjie, Zeyu Sun, Qihao Zhu, Ge Li, Shaowei Cai, Yingfei Xiong, and Lu Zhang.

  19. Optimistic tree search strategies for black-box combinatorial optimization NeurIPS, 2022. paper

    Malherbe, Cedric and Grosnit, Antoine and Tutunov, Rasul and Ammar, Haitham Bou and Wang, Jun

  20. Goal-Aware Neural SAT Solver. IJCNN, 2022. paper

    Ozolins, Emils, Karlis Freivalds, Andis Draguns, Eliza Gaile, Ronalds Zakovskis, and Sergejs Kozlovics.

  21. NeuroComb: Improving SAT Solving with Graph Neural Networks. Arxiv, 2022. paper

    Wang, Wenxi, Yang Hu, Mohit Tiwari, Sarfraz Khurshid, Kenneth McMillan, and Risto Miikkulainen.

  22. On the Performance of Deep Generative Models of Realistic SAT Instances. SAT, 2022. paper

    Garzón, Iván, Pablo Mesejo, and Jesús Giráldez-Cru.

  23. DeepSAT: An EDA-Driven Learning Framework for SAT. Arxiv, 2022. paper

    Li, Min, Zhengyuan Shi, Qiuxia Lai, Sadaf Khan, and Qiang Xu.

  24. SATformer: Transformers for SAT Solving. Arxiv, 2022. paper

    Shi, Zhengyuan, Min Li, Sadaf Khan, Hui-Ling Zhen, Mingxuan Yuan, and Qiang Xu.

  25. Augment with Care: Contrastive Learning for Combinatorial Problems. ICML, 2022. paper, code

    Duan, Haonan, Pashootan Vaezipoor, Max B. Paulus, Yangjun Ruan and Chris J. Maddison

  26. NSNet: A General Neural Probabilistic Framework for Satisfiability Problems NeurIPS, 2022. paper

    Zhaoyu Li, Xujie Si

  27. Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions NeurIPS, 2022. paper

    Nikolaos Karalias, Joshua Robinson, Andreas Loukas, Stefanie Jegelka

  28. Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness ICLR, 2022. paper

    Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski and Stephan Günnemann

  29. Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets NeurIPS, 2023. paper, code

    Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron Courville, Yoshua Bengio, Ling Pan

  30. ⭐HardSATGEN: Understanding the Difficulty of Hard SAT Formula Generation and A Strong Structure-Hardness-Aware Baseline KDD, 2023. paper, code

    Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, Junchi Yan

  31. Distributed Constrained Combinatorial Optimization leveraging Hypergraph Neural Networks Nature Machine Intelligence, 2024. paper, code

    Nasimeh Heydaribeni, Xinrui Zhan, Ruisi Zhang, Tina Eliassi-Rad, Farinaz Koushanfar

  32. Efficient Combinatorial Optimization via Heat Diffusion NeurIPS, 2024. paper

    Hengyuan Ma, Wenlian Lu, Jianfeng Feng

  33. ⭐UniCO: On Unified Combinatorial Optimization via Problem Reduction to Matrix-Encoded General TSP ICLR, 2025. paper, code

    Wenzheng Pan, Hao Xiong, Jiale Ma, Wentao Zhao, Yang Li, Junchi Yan

Tags:
Categories: