Heuristics for dynamically adapting propagation in constraint satisfaction problems

Article type: Research Article

Authors: Stergiou, Kostas

Affiliations: Department of Information & Communication Systems Engineering, University of the Aegean, Aegean, Greece. E-mail: konsterg@aegean.gr

Abstract: Building adaptive constraint solvers is a major challenge in constraint programming. An important line of research towards 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 heuristic approach to this problem based on the monitoring of propagation events like value deletions and domain wipeouts. We develop a number of heuristics that allow the constraint 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 approach is based on the observation that propagation events for individual constraints in structured problems mostly occur in clusters of nearby revisions. Hence, parts of the search space where certain constraints are highly active can be identified 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 propagation 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 effectiveness of the proposed heuristics.

Keywords: Constraint programming, search, constraint propagation

DOI: 10.3233/AIC-2009-0450

Journal: AI Communications, vol. 22, no. 3, pp. 125-141, 2009