Constraint processing incorporating, back jumping, learning, and cutset-decomposition

Researchers in the areas of constraint-satisfaction problems (CSPs), logic programming, and truth-maintenance systems have suggested various schemes for enhancing the performance of backtrack algorithms. The author defines and compares the performance of three such schemes: backjump, learning while searching, and the cycle-cutset method. Backjump and cycle-cutset work best when the constraint graph is sparse, while the learning scheme mostly benefits problem instances with dense constraint graphs. An integrated strategy is proposed 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% over any of the individual schemes