Learning Heuristics for Quantified Boolean Formulas through Reinforcement Learning
Keywords: Logic, QBF, Logical Reasoning, SAT, Graph, Reinforcement Learning, GNN
TL;DR: We use RL to automatically learn branching heuristic within a state of the art QBF solver, on industrial problems.
Abstract: We demonstrate how to learn efficient heuristics for automated reasoning algorithms for quantified Boolean formulas through deep reinforcement learning. We focus on a backtracking search algorithm, which can already solve formulas of impressive size - up to hundreds of thousands of variables. The main challenge is to find a representation of these formulas that lends itself to making predictions in a scalable way. For a family of challenging problems, we learned a heuristic that solves significantly more formulas compared to the existing handwritten heuristics.
Original Pdf: pdf
8 Replies
Loading