Poster
Learning Local Search Heuristics for Boolean Satisfiability
Emre Yolcu · Barnabas Poczos
Keywords: [ Reinforcement Learning ] [ Reinforcement Learning and Planning ] [ Stochastic Optimization ] [ Optimization -> Combinatorial Optimization; Optimization ]
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.