Improving SAT Solver Heuristics with Graph Networks and Reinforcement Learning

2019-09-25 · Vitaly Kurin, Saad Godil, Shimon Whiteson, Bryan Catanzaro

We present GQSAT, a branching heuristic in a Boolean SAT solver trained with value-based reinforcement learning (RL) using Graph Neural Networks for function approximation. Solvers using GQSAT are complete SAT solvers that either provide a satisfying assignment or a proof of unsatisfiability, which is required for many SAT applications. The branching heuristic commonly used in SAT solvers today suffers from bad decisions during their warm-up period, whereas GQSAT has been trained to examine the structure of the particular problem instance to make better decisions at the beginning of the search. Training GQSAT is data efficient and does not require elaborate dataset preparation or feature engineering to train. We train GQSAT on small SAT problems using RL interfacing with an existing SAT solver. We show that GQSAT is able to reduce the number of iterations required to solve SAT problems by 2-3X, and it generalizes to unsatisfiable SAT instances, as well as to problems with 5X more variables than it was trained on. We also show that, to a lesser extent, it generalizes to SAT problems from different domains by evaluating it on graph coloring. Our experiments show that augmenting SAT solvers with agents trained with RL and graph neural networks can improve performance on the SAT search problem.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Tasks

Feature Engineering reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Learning from Algorithm Feedback: One-Shot SAT Solver Guidance with GNNs

2025-05-21 · Jan Tönshoff, Martin Grohe

Boolean Satisfiability (SAT) solvers are foundational to computer science, yet their performance typically hinges on hand-crafted heuristics. This work introduces Reinforcement Learning from Algorithm Feedback (RLAF) as …

Combinatorial Optimization Policy Gradient Methods reinforcement-learning Reinforcement Learning

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…

Deep Reinforcement Learning Graph Neural Network reinforcement-learning Reinforcement Learning+2

Reinforcement Learning for Integer Programming: Learning to Cut

2019-06-11 · ICML 2020 1 · Yunhao Tang, Shipra Agrawal, Yuri Faenza

Integer programming (IP) is a general optimization framework widely applicable to a variety of unstructured and structured problems arising in, e.g., scheduling, production planning, and graph optimization. As IP models …

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Scheduling

Can Q-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver?

2020-12-01 · NeurIPS 2020 12 · Vitaly Kurin, Saad Godil, Shimon Whiteson, Bryan Catanzaro

We present Graph-Q-SAT, a branching heuristic for a Boolean SAT solver trained with value-based reinforcement learning (RL) using Graph Neural Networks for function approximation. Solvers using Graph-Q-SAT are complete S…

Feature Engineering Q-Learning Reinforcement Learning (RL)

Can $Q$-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver?

2019-09-26 · Vitaly Kurin, Saad Godil, Shimon Whiteson, Bryan Catanzaro

We present Graph-$Q$-SAT, a branching heuristic for a Boolean SAT solver trained with value-based reinforcement learning (RL) using Graph Neural Networks for function approximation. Solvers using Graph-$Q$-SAT are comple…

Feature Engineering Q-Learning Reinforcement Learning Reinforcement Learning (RL)