On Continuous Local BDD-Based Search for Hybrid SAT Solving

Authors

  • Anastasios Kyrillidis Rice University
  • Moshe Vardi Rice University
  • Zhiwei Zhang Rice University

Keywords:

Satisfiability, Constraint Optimization, Constraint Satisfaction, Mixed Discrete/Continuous Optimization

Abstract

We explore the potential of continuous local search (CLS) in SAT solving by proposing a novel approach for finding a solution of a hybrid system of Boolean constraints. The algorithm is based on CLS combined with belief propagation on binary decision diagrams (BDDs). Our framework accepts all Boolean constraints that admit compact BDDs, including symmetric Boolean constraints and small-coefficient pseudo-Boolean constraints as interesting families. We propose a novel algorithm for efficiently computing the gradient needed by CLS. We study the capabilities and limitations of our versatile CLS solver, GradSAT, by applying it on many benchmark instances. The experimental results indicate that GradSAT can be a useful addition to the portfolio of existing SAT and MaxSAT solvers for solving Boolean satisfiability and optimization problems.

Downloads

Published

2021-05-18

How to Cite

Kyrillidis, A., Vardi, M., & Zhang, Z. (2021). On Continuous Local BDD-Based Search for Hybrid SAT Solving. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5), 3841-3850. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16502

Issue

Section

AAAI Technical Track on Constraint Satisfaction and Optimization