Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition

摘要

Researchers in the areas of constraint satisfaction problems, logic programming, and truth maintenance systems have suggested various schemes for enhancing the performance of the backtracking algorithm. This paper defines and compares the performance of three such schemes: “backjumping,” “learning,” and “cycle-cutset.” The backjumping and the cycle-cutset methods work best when the constraint graph is sparse, while the learning scheme mostly benefits problem instances with dense constraint graphs. An integrated strategy is described which utilizes the distinct advantages of each scheme. Experiments show that, in hard problems, the average improvement realized by the integrated scheme is 20–25% higher than any of the individual schemes.