Timezone: »

 
Poster
Learning Local Search Heuristics for Boolean Satisfiability
Emre Yolcu · Barnabas Poczos

Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #177
in Optimization -- Combinatorial 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.

Keywords: Reinforcement Learning · Reinforcement Learning and Planning · Stochastic Optimization · Optimization -> Combinatorial Optimization; Optimization
[ Paper]  [ Slides] 

Author Information

Emre Yolcu (Carnegie Mellon University)
Barnabas Poczos (Carnegie Mellon University)

More from the Same Authors