Affiliations: School of Computer Science, University of St. Andrews, Scotland, UK. E-mails: {ian.gent, ijm}@st-andrews.ac.uk | Adobe, Edinburgh, Scotland, UK. E-mail: neil@bigoh.co.uk
Note: [] Corresponding author: Ian P. Gent, School of Computer Science, University of St. Andrews, St. Andrews, Scotland, UK. E-mail: ian.gent@st-andrews.ac.uk.
Abstract: 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.
