Domain Filtering Can Degrade Intelligent Backtracking Search

Abstract

This paper presents an improved backjumping algorithm for the constraint satisfaction problem, namely conflict-directed backjumping (CBJ). CBJ is then modified such that it can detect infeasible values and removes them from the domains of variables once and for all. A similar modification is then made to Gaschnig's backjumping routine BJ and to Haralick and Elliott's forward checking routine FC. Empirical analysis shows that these modifications tend to result in an improvement in average performance. The existence of a peculiar phenomenon is then shown: the removal of infeasible values may result in a degradation in the performance of intelligent backjumping algorithms, and conversely the addition of infeasible values may lead to an improvement in performance.