NeuroCore: Guiding CDCL with Unsat-Core Predictions

03/12/2019
by   Daniel Selsam, et al.
0

The NeuroSAT neural network architecture was recently introduced for predicting properties of propositional formulae. When trained to predict the satisfiability of toy problems, it was shown to find solutions and unsatisiable cores on its own. However, the authors saw "no obvious path" to using the architecture to improve the state-of-the-art. In this work, we train a simplified NeuroSAT architecture to directly predict the unsatisfiable cores of real problems, and modify MiniSat to periodically replace its variable activity scores with NeuroSAT's prediction of how likely they are to appear in an unsatisfiable core. Our modified MiniSat solves 10 2018 than the original does. Although MiniSat is no longer considered a state-of-the-art solver, our results nonetheless demonstrate the potential for NeuroSAT (and in particular, NeuroCore) to provide useful guidance to CDCL solvers on real problems.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset