Learning Local Search Heuristics for Boolean Satisfiability

2019-12-01 · NeurIPS 2019 12 · Emre Yolcu, Barnabas Poczos

We present an approach to learn SAT solver heuristics from scratch through deep reinforcement learning with a curriculum. In particular, we incorporate a graph neural network in a stochastic local search algorithm to act as the variable selection heuristic. We consider Boolean satisfiability problems from different classes and learn specialized heuristics for each class. Although we do not aim to compete with the state-of-the-art SAT solvers in run time, we demonstrate that the learned heuristics allow us to find satisfying assignments in fewer steps compared to a generic heuristic, and we provide analysis of our results through experiments.

📄 PDF Abstract BibTeX

Code (1)

emreyolcu/sat 공식 구현 pytorch

Tasks

Deep Reinforcement LearningGraph Neural Network reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Variable Selection

Methods 이 논문이 사용한 방법론

Graph Neural Network 설명 없음

Machine Learning Methods in Solving the Boolean Satisfiability Problem

2022-03-02 · Wenxuan Guo, Junchi Yan, Hui-Ling Zhen, Xijun Li 외

This paper reviews the recent literature on solving the Boolean satisfiability problem (SAT), an archetypal NP-complete problem, with the help of machine learning techniques. Despite the great success of modern SAT solve…

BIG-bench Machine Learning

A Probabilistic Approach to Satisfiability of Propositional Logic Formulae

2019-12-04 · Reazul Hasan Russel

We propose a version of WalkSAT algorithm, named as BetaWalkSAT. This method uses probabilistic reasoning for biasing the starting state of the local search algorithm. Beta distribution is used to model the belief over b…

New Boolean satisfiability problem heuristic strategy: Minimal Positive Negative Product Strategy

2023-10-26 · Qun Zhao, Xintao Wang, Menghui Yang

This study presents a novel heuristic algorithm called the "Minimal Positive Negative Product Strategy" to guide the CDCL algorithm in solving the Boolean satisfiability problem. It provides a mathematical explanation fo…

Graph Neural Networks for Reasoning 2-Quantified Boolean Formulas

2019-09-25 · Fei Wang, Zhanfu Yang, Ziliang Chen, Guannan Wei 외

It is valuable yet remains challenging to apply neural networks in logical reasoning tasks. Despite some successes witnessed in learning SAT (Boolean Satisfiability) solvers for propositional logic via Graph Neural Netwo…

Logical Reasoning

Learning Interpretable Heuristics for WalkSAT

2023-07-10 · Yannet Interian, Sara Bernardini

Local search algorithms are well-known methods for solving large, hard instances of the satisfiability problem (SAT). The performance of these algorithms crucially depends on heuristics for setting noise parameters and s…

reinforcement-learning