Conflict-directed backjumping revisited

In recent years, many improvements to backtracking algorithms for solving c onstraint satisfaction problems have been proposed. The techniques for impr oving backtracking algorithms can be conveniently classified as look-ahead schemes and look-back schemes. Unfortunately, look-ahead and look-back sche mes are not entirely orthogonal as it has been observed empirically that th e enhancement of look-ahead techniques is sometimes counterproductive to th e effects of look-back techniques. In this paper, we focus on the relations hip between the two most important look-ahead techniques-using a variable o rdering heuristic and maintaining a level of local consistency during the b acktracking search-and the look-back technique of conflict-directed backjum ping (CBJ). We show that there exists a "perfect" dynamic variable ordering such that CBJ becomes redundant. We also show theoretically that as the le vel of local consistency that is maintained in the backtracking search is i ncreased, the less that backjumping will be an improvement. Our theoretical results partially explain why a backtracking algorithm doing more in the l ook-ahead phase cannot benefit more from the backjumping look-back scheme. Finally, we show empirically that adding CBJ to a backtracking algorithm th at maintains generalized arc consistency (GAC), an algorithm that we refer to as GAC-CBJ, can still provide orders of magnitude speedups. Our empirica l results contrast with Bessiere and Regin's conclusion (1996) that CBJ is useless to an algorithm that maintains arc consistency.