Background Conflict-Driven Clause Learning

1 background

1.1 boolean satisfiability problem
1.2 unit clause rule (unit propagation)
1.3 boolean constraint propagation (bcp)
1.4 resolution
1.5 dp algorithm
1.6 dpll algorithm

background

background knowledge following issues needed have clear idea cdcl algorithm.

boolean satisfiability problem

the satisfiability problem consists in finding satisfying assignment given formula in conjunctive normal form (cnf).

an example of such formula is:

( (not a) or (not c) )   ,   (b or c),

or, using common notation:

(

a
′

+

c
′

)
(
b
+
c
)


{\displaystyle (a +c )(b+c)}

where a,b,c boolean variables,




a
′



{\displaystyle }

,




c
′



{\displaystyle c }

,



b


{\displaystyle b}

, ,



c


{\displaystyle c}

literals, ,




a
′

+

c
′



{\displaystyle +c }

,



b
+
c


{\displaystyle b+c}

clauses.

a satisfying assignment formula e.g.:

a
=
f
a
l
s
e
,
b
=
f
a
l
s
e
,
c
=
t
r
u
e


{\displaystyle a=false,b=false,c=true}

since makes first clause true (since




a
′



{\displaystyle }

true) second 1 (since



c


{\displaystyle c}

true).

this examples uses 3 variables (a, b, c), , there 2 possible assignments (true , false) each of them. 1 has




2

3


=
8


{\displaystyle 2^{3}=8}

possibilities. in small example, 1 can use brute-force search try possible assignments , check if satisfy formula. in realistic applications millions of variables , clauses brute force search impractical. responsibility of sat solver find satisfying assignment efficiently , applying different heuristics complex cnf formulas.

unit clause rule (unit propagation)

if unsatisfied clause has 1 of literals or variables evaluated @ false, free literal must true in order clause true. example, if below unsatisfied clause evaluated



a
=
f
a
l
s
e


{\displaystyle a=false}

,



b
=
f
a
l
s
e


{\displaystyle b=false}

must have



c
=
t
r
u
e


{\displaystyle c=true}

in order clause



(
a
∨
b
∨
c
)


{\displaystyle (a\lor b\lor c)}

true.

boolean constraint propagation (bcp)

the iterated application of unit clause rule referred unit propagation or boolean constraint propagation (bcp).

resolution

consider 2 clauses



(
a
∨
b
∨
c
)


{\displaystyle (a\lor b\lor c)}

,



(
¬
c
∨
d
∨
¬
e
)


{\displaystyle (\neg c\lor d\lor \neg e)}

. clause



(
a
∨
b
∨
d
∨
¬
e
)


{\displaystyle (a\lor b\lor d\lor \neg e)}

, obtained merging 2 clauses , removing both



¬
c


{\displaystyle \neg c}

,



c


{\displaystyle c}

, called resolvent of 2 clauses.

dp algorithm

the dp algorithm has been introduced davis , putnam in 1960. informally, algorithm iteratively performs following steps until no more variables left in formula:

select variable



a


{\displaystyle a}

, add non-tautological resolvents upon



a


{\displaystyle a}

(a resolvent non-tautological if not contain



v


{\displaystyle v}

,



¬
v


{\displaystyle \neg v}

variable



v


{\displaystyle v}

).
remove original clauses contain



a


{\displaystyle a}

.

see more details here dp algorithm

dpll algorithm

davis, putnam, logemann, loveland (1962) had developed algorithm. properties of algorithms are:

it based on search.
it basis modern sat solvers.
it uses learning , chronological backtracking (1996).

see more details @ dpll algorithm. example visualization of dpll algorithm having chronological backtracking: