Nikolaj Bjørner

Daniel Selsam, Nikolaj Bjørner

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 unsatisfiable 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. We modify several high-performance SAT solvers to periodically replace their variable activity scores with NeuroSAT's prediction of how likely the variables are to appear in an unsatisfiable core. The modified MiniSat solves 10% more problems on SAT-COMP 2018 within the standard 5,000 second timeout than the original does. The modified Glucose solves 11% more problems than the original, while the modified Z3 solves 6% more. The gains are even greater when the training is specialized for a specific distribution of problems; on a benchmark of hard problems from a scheduling domain, the modified Glucose solves 20% more problems than the original does within a one-hour timeout. Our results demonstrate that NeuroSAT can provide effective guidance to high-performance SAT solvers on real problems.

Nikolaj Bjørner, Fabio Fioravanti, Andrey Rybalchenko et al.

This volume contains the proceedings of HCVS 2014, the First Workshop on Horn Clauses for Verification and Synthesis which was held on July 17, 2014 in Vienna, Austria as a satellite event of the Federated Logic Conference (FLoC) and part of the Vienna Summer of Logic (VSL 2014). HCVS 2014 was affiliated to the 26th International Conference on Computer Aided Verification (CAV 2014) and to the 30th International Conference on Logic Programming (ICLP 2014). Most Program Verification and Synthesis problems of interest can be modeled directly using Horn clauses and many recent advances in the Constraint/Logic Programming and Program Verification communities have centered around efficiently solving problems presented as Horn clauses. Since Horn clauses for verification and synthesis have been advocated by these communities in different times and from different perspectives, the HCVS workshop was organized to stimulate interaction and a fruitful exchange and integration of experiences.