Conflict-driven clause learning

submited by
Style Pass
2023-11-19 00:00:08

In computer science, conflict-driven clause learning (CDCL) is an algorithm for solving the Boolean satisfiability problem (SAT). Given a Boolean formula, the SAT problem asks for an assignment of variables so that the entire formula evaluates to true. The internal workings of CDCL SAT solvers were inspired by DPLL solvers. The main difference between CDCL and DPLL is that CDCL's back jumping is non-chronological.

Conflict-driven clause learning was proposed by Marques-Silva and Karem A. Sakallah (1996, 1999)[1][2] and Bayardo and Schrag (1997).[3]

where A,B,C are Boolean variables, ¬ A {\displaystyle \lnot A} , ¬ C {\displaystyle \lnot C} , B {\displaystyle B} , and C {\displaystyle C} are literals, and ¬ A ∨ ¬ C {\displaystyle \lnot A\lor \lnot C} and B ∨ C {\displaystyle B\lor C} are clauses.

since it makes the first clause true (since ¬ A {\displaystyle \lnot A} is true) as well as the second one (since C {\displaystyle C} is true).

Leave a Comment