An empirical study of learning and forgetting constraints

Conflict-driven constraint learning provides big gains on many CSP and SAT problems. However, time and space costs to propagate the learned constraints can grow very quickly, so constraints are often discarded (forgotten) to reduce overhead. We conduct a major empirical investigation into the overhe...

Full description

Saved in:
Bibliographic Details
Published in:Ai communications 2012-01, Vol.25 (2), p.191-208
Main Authors: Gent, Ian P., Miguel, Ian, Moore, Neil C.A.
Format: Article
Language:English
Subjects:
Artificial intelligence
Combinatorial analysis
Empirical analysis
Explosions
Gain
Learning
Machine learning
Solvers
Workshops
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Conflict-driven constraint learning provides big gains on many CSP and SAT problems. However, time and space costs to propagate the learned constraints can grow very quickly, so constraints are often discarded (forgotten) to reduce overhead. We conduct a major empirical investigation into the overheads introduced by unbounded constraint learning in CSP. To the best of our knowledge, this is the first published study in either CSP or SAT. We obtain three significant results. The first is that a small percentage of learnt constraints do most propagation. While this is conventional wisdom, it has not previously been the subject of empirical study. Second, we show that even constraints that do no effective propagation can incur significant time overheads. Finally, by implementing forgetting, we confirm that it can significantly improve the performance of modern learning CSP solvers, contradicting some previous research.
ISSN:0921-7126
DOI:10.3233/AIC-2012-0524