26/04/2020

Learning Heuristics for Quantified Boolean Formulas through Reinforcement Learning

Gil Lederman, Markus Rabe, Sanjit Seshia, Edward A. Lee

Keywords: Logic, QBF, Logical Reasoning, SAT, Graph, Reinforcement Learning, GNN

Abstract Paper Similar Papers

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.

 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at ICLR 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 13:21 
 0
 0
 0
 0
 15:00 
 0
 0
 0
 0
 3:24 
 0
 0
 0
 0
 20:40 
 0
 0
 0
 0
 3:37 
 0
 0
 0
 0
 5:16 
 0
 0
 0
 0
 5:07 
 0
 0
 0
 0
 15:23 
 0
 0
 0
 0
 11:33 
 0
 0
 0
 0
 8:40 
 0
 0
 0
 0
 12:36 
 0
 0
 0
 0
 18:01 
 0
 0
 0
 0
 5:12 
 0
 0
 0
 0
 19:42 
 0
 0
 0
 0
 4:50 
 0
 0
 0
 0
 5:05 
 0
 0
 0
 0
 3:12 
 0
 0
 0
 0
 14:26 
 0
 0
 0
 0
 6:02 
 0
 0
 0
 0
 5:14 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 10:26 
 0
 0
 0
 0
 3:54 
 0
 0
 0
 0
 16:35 
 0
 0
 0
 0
 14:49 
 0
 0
 0
 0
 14:18 
 0
 0
 0
 0
 10:12 
 0
 0
 0
 0
 14:52 
 0
 0
 0
 0
 7:16 
 0
 0
 0
 0
 14:50 
 0
 0
 0
 0
 15:29 
 0
 0
 0
 0
 15:17 
 0
 0
 0
 0
 5:18 
 0
 0
 0
 0
 14:01 
 0
 0
 0
 0
 11:27 
 0
 0
 0
 0
 7:27 
 0
 0
 0
 0
 20:30 
 0
 0
 0
 0
 12:15 
 0
 0
 0
 0
 19:44 
 0
 0
 0
 0
 6:48