Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
sav08:advanced_sat_solving_techniques [2008/03/12 21:34] vkuncak |
sav08:advanced_sat_solving_techniques [2010/03/02 15:25] (current) piskac |
||
|---|---|---|---|
| Line 45: | Line 45: | ||
| Need efficient data structures: | Need efficient data structures: | ||
| + | * counters: simple, need many updates | ||
| * head/tail list | * head/tail list | ||
| - | * two-literal watching | + | * two-literal watching: each var has list of unassigned literals, do search to see if there are other literals to watch in clause |
| + | * invariant: each non-conflicting clause has at least one watched literal, but not all literals need to be watched | ||
| + | * no need to do anything on backtrack | ||
| - | Other mechanisms less important: e.g. propagating equivalences. | + | Mechanisms other than unit propagation are less important: e.g. propagating equivalences. |
| ===== Conflict Analysis and Lemma Learning - analyze_conflict() ===== | ===== Conflict Analysis and Lemma Learning - analyze_conflict() ===== | ||
| Line 66: | Line 69: | ||
| 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 79: | Line 82: | ||
| * deduction rule was that some original clause C became unit clause because all literals exept literal containing var were false | * deduction rule was that some original clause C became unit clause because all literals exept literal containing var were false | ||
| * then antecedant(var) is C | * then antecedant(var) is C | ||
| + | |||
| + | asserting clause: | ||
| + | * false at current decision level | ||
| + | * only one literal has current decision level (others were assigned before) | ||
| + | |||
| + | If c1 is not asserting clause yet, we resolve it with antecedants of variables, following backwards deduction steps. | ||
| + | |||
| + | In other words: we remove variables at current decision level until only one at the current is left. | ||
| + | |||
| + | The clause forces a different value of a decision variable at a previous level. | ||
| ===== Storing Clauses ===== | ===== Storing Clauses ===== | ||
| Line 89: | Line 102: | ||
| Restart: if no progress for a while, start over (keeping some lemmas), will most likely do different branching. | Restart: if no progress for a while, start over (keeping some lemmas), will most likely do different branching. | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== Some Relevant Papers ===== | ||
| + | |||
| + | * [[http://portal.acm.org/citation.cfm?id=1217859|Solving SAT and SAT Modulo Theories: From an abstract Davis--Putnam--Logemann--Loveland procedure to DPLL(T)]] | ||
| + | |||
| + | * [[http://www.csee.ogi.edu/~krstics/smtarch.pdf|Architecting Solvers for SAT Modulo Theories: Nelson-Oppen with DPLL]] | ||
| + | |||
| ===== Other Techniques ===== | ===== Other Techniques ===== | ||
| - | * [[http://www.princeton.edu/~chaff/publication/cade_cav_2002.pdf|The Quest for Efficient Boolean Satisfiability Solvers]] | + | * [[http://www.princeton.edu/~chaff/publication/cade_cav_2002.pdf|The Quest for Efficient Boolean Satisfiability Solvers]], {{sav08:cade_cav_2002.pdf|pdf}} |