Tech Report CS-06-09

Randomized Filtering Algorithms

Irit Katriel and Pascal Van Hentenryck

June 2006

Abstract:

Filtering every global constraint of a CSP to arc consistency at every search step can be costly and solvers often compromise on either the level of consistency or the frequency at which arc consistency is enforced.

In this paper we propose two randomized filtering schemes for dense instances of AllDifferent and its generalization, the global cardinality constraint. The first delayed filtering scheme is a Monte Carlo algorithm: its running time is superior, in the worst case, to that of enforcing arc consistency after every domain event, while its filtering effectiveness is analyzed in the expected sense. The second scheme is a Las Vegas algorithm using filtering triggers: Its effectiveness is the same as enforcing arc consistency after every domain event, while its running time improves in the expected sense.

(complete text in pdf or gzipped postscript)