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/13 10:43] vkuncak |
sav08:advanced_sat_solving_techniques [2010/03/02 15:25] piskac |
||
---|---|---|---|
Line 48: | Line 48: | ||
* head/tail list | * head/tail list | ||
* two-literal watching: each var has list of unassigned literals, do search to see if there are other literals to watch in clause | * 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 clause has at least one watched literal, but not all literals need to be watched | + | * 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 | ||
Mechanisms other than unit propagation are less important: e.g. propagating equivalences. | Mechanisms other than unit propagation are less important: e.g. propagating equivalences. | ||
Line 87: | Line 88: | ||
If c1 is not asserting clause yet, we resolve it with antecedants of variables, following backwards deduction steps. | 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. | The clause forces a different value of a decision variable at a previous level. | ||
Line 99: | 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}} |