Dead-end driven learning

Abstract

The paper evaluates the effectiveness of learning for speeding up the solution of constraint satisfaction problems. It extends previous work (Dechter 1990) by introducing a new and powerful variant of learning and by presenting an extensive empirical study on much larger and more difficult problem instances. Our results show that learning can speed up backjumping when using either a fixed or dynamic variable ordering. However, the improvement with a dynamic variable ordering is not as great, and for some classes of problems learning is helpful only when a limit is placed on the size of new constraints learned.