Quick Shaving

Olivier Lhomme

Arc-consistency plays such a key role in constraint programming for solving real life problems that it is almost the only algorithm used for reducing domains. There are a few specific problems for which a stronger form of propagation, often called shaving, is more efficient. Nevertheless, in many cases, shaving at each node of the search tree is not worth doing: arc-consistency filtering is much faster, and the additional domain reductions inferred by shaving do not pay off. In this paper, we propose a new kind of shaving called QuickShaving, which is guided by the search. As QuickShaving may infer some additional domain reductions compared with arc-consistency, it can improve the search for a solution by an exponential ratio. Moreover, the advantage of QuickShaving is that in practice, unlike a standard form of shaving, the additional domain reductions deduced by QuickShaving come at a very low overhead compared with arc-consistency.

Content Area: 6. Constraint Satisfaction and Satisfiability

Subjects: 15.2 Constraint Satisfaction; 15.7 Search

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.