National Conference on Artificial Intelligence · 2005 · 84 citations · 11 references
ComputingComputer ScienceAlgorithmsFormal MethodsKnowledge RepresentationConstraint SatisfactionConstraint SolvingAutomated Reasoning With ConstraintsConstraintsCsp SolvingLearning
Although nogood learning in CSPs and clause learning in SAT are formally equivalent, nogood learning has not been as successful a technique in CSP solvers as clause learning has been for SAT solvers. We show that part of the reason for this discrepancy is that nogoods in CSPs (as standardly defined) are too restrictive. In this paper we demonstrate that these restrictions can be lifted so that a CSP solver can learn more general and powerful nogoods. Nogoods generalized in this manner yield a provably more powerful CSP solver. We also demonstrate how generalized nogoods facilitate learning useful nogoods from global constraints. Finally, we demonstrate empirically that generalized nogoods can yield significant improvements in performance.
11
Matthew W. Moskewicz, Conor Madigan, Ying Zhao et al. · 2001 · 2.9K citations
Efficient Conflict Driven Learning in a Boolean Satisfiability Solver
2001 · 666 citations
Using CSP look-back techniques to solve real-world SAT instances
Roberto J. Bayardo, Robert Schrag · 1997 · 598 citations
HYBRID ALGORITHMS FOR THE CONSTRAINT SATISFACTION PROBLEM
Patrick Prosser · Computational Intelligence · 1993 · 519 citations