  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.
