Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
sav08:advanced_sat_solving_techniques [2008/03/12 21:19] vkuncak |
sav08:advanced_sat_solving_techniques [2008/03/12 21:40] vkuncak |
||
---|---|---|---|
Line 22: | Line 22: | ||
} | } | ||
</code> | </code> | ||
+ | |||
+ | ===== Branching Heuristics - decide_next_branch() ===== | ||
+ | |||
+ | Decision level: each variable whose value is chosed increase decision level. | ||
+ | |||
+ | Score variables: if a variable participates in deriving lemmas triggered by a conflict, increase its score. | ||
+ | * decrease existing scores gradually over time | ||
===== Deduction Algorithm - deduce() ===== | ===== Deduction Algorithm - deduce() ===== | ||
Main: Boolean Constraint Propagation (BCP), also called unit propagation. | Main: Boolean Constraint Propagation (BCP), also called unit propagation. | ||
+ | |||
+ | Deduced variables have same decision level as the last decision variable. | ||
+ | |||
+ | === Data Structures === | ||
++Problem with deleting clauses and literals:|backtracking is expensive.++ | ++Problem with deleting clauses and literals:|backtracking is expensive.++ | ||
+ | |||
+ | Instead: maintain truth value of literals in current assignment. | ||
+ | |||
+ | We always work with original clauses (we just record how many literals are false) | ||
Need efficient data structures: | Need efficient data structures: | ||
Line 51: | Line 66: | ||
analyze_conflict() { | analyze_conflict() { | ||
cl = find_conflicting_clause(); | cl = find_conflicting_clause(); | ||
- | while (!stop_criterion_met(c1)) { | + | while (!is_asserting_clause(c1)) { |
var = var_of_lit(choose_literal(c1)); | var = var_of_lit(choose_literal(c1)); | ||
c1 = resolve(c1, antecedant(var), var); | c1 = resolve(c1, antecedant(var), var); | ||
Line 65: | Line 80: | ||
* then antecedant(var) is C | * then antecedant(var) is C | ||
- | ===== Branching Heuristics - decide_next_branch() ===== | + | asserting clause: |
+ | * false at current decision level | ||
+ | * only one literal has current decision level (others were assigned before) | ||
- | Score variables: if a variable caused a conflict, increase its score. | + | If c1 is not asserting clause yet, we resolve it with antecedants of variables, following backwards deduction steps. |
- | * decrease existing scores gradually over time | + | |
+ | The clause forces a different value of a decision variable at a previous level. | ||
===== Storing Clauses ===== | ===== Storing Clauses ===== |