Some Practicable Filtering Techniques for the Constraint Satisfaction Problem

Abstract

Filtering techniques are essential in order to efficiently solve constraint satisfaction problems (CSPs). A blind search often leads to a combinatorial explosion, the algorithm repeatedly finding the same local inconsistencies. Maintaining a local consistency can strongly reduce the search effort especially on hard and large problems. A good illustration are the good time performances on such problems of maintaining arc consistency during search compared to forward checking which maintains a lower level of local consistency. On the one hand, arc consistency (2-consistency) is the most used filtering technique because it cheaply removes some values that cannot belong to any solution. On the other hand, other k-consistencies (k >= 3) have important space and time requirements because they can change the set of constraints. They can only be used on very small CSPs. Thus, in this paper, we study and compare the filtering techniques that are more pruningful than arc consistency while leaving unchanged the set of constraints. As arc consistency, they only remove inconsistent values in the domains, and so, can deal with large CSPs.