Generalized NoGoods in CSPs

George Katsirelos, Fahiem Bacchus

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.

Content Area: 6. Constraint Satisfaction and Satisfiability

Subjects: 15.2 Constraint Satisfaction

Submitted: May 10, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.