1Heuristics for Dynamically Adapting Propagation in Constraint Satisfaction Problems

Building adaptive constraint solvers is a major challenge in constraint programming. An important line of research to-wards this goal is concerned with ways to dynamically adapt the propagation method applied on the constraints of the problem during search. In this paper we present a heuris-tic approach to this problem based on the monitoring of propagation events like value deletions and domain wipe-outs. We develop a number of heuristics that allow the con-straint solver to dynamically switch between a weaker and cheap local consistency and a stronger, but more expensive one, when certain conditions are met. The success of this ap-proach is based on the observation that propagation events for individual constraints in structured problems mostly oc-cur in clusters of nearby revisions. Hence, parts of the search space where certain constraints are highly active can be iden-tified and exploited paving the way for the informed use of constraint propagation techniques. In this paper we first give some experimental results displaying the clustering of prop-agation events in structured binary CSPs. Then we present simple heuristics that exploit this clustering to efficiently switch between different local consistencies on individual constraints during search. Finally, we make an experimental study on various binary CSPs demonstrating the effective-ness of the proposed heuristics