Exploiting weak dependencies in tree-based search

ABSTRACT

In this work, our objective is to heuristically discover a simplified form of functional dependencies between variables called weak dependencies. Once discovered, these relations are used to rank the variables. Our method shows that these relations can be detected with some acceptable overhead during constraint propagation. More precisely, each time a variable y gets instantiated as a result of the instantiation of x, a weak dependency (x, y) is recorded. As a consequence, the weight of x is raised, and the variable becomes more likely to be selected by the variable ordering heuristic. Experiments on a large set of problems show that on the average, the search trees are reduced by a factor 3 while runtime is decreased by 31% when compared against dom-wdeg, one of the best dynamic variable ordering heuristic.

REFERENCES

• 1: Dimitris Achlioptas , Carla P. Gomes , Henry A. Kautz , Bart Selman, Generating Satisfiable Problem Instances, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.256-261, July 30-August 03, 2000
• 2: F. Boussemart, F. Hemery, C. Lecoutre, and L. Sais. Boosting systematic search by weighting constraints. In ICAI, pages 146--150, 2004.
• 3: Daniel Brélaz, New methods to color the vertices of a graph, Communications of the ACM, v.22 n.4, p.251-256, April 1979 [doi>10.1145/359094.359101]
• 4: B. N. Dilkina, C. P. Gomes, and A. Sabharwal. Tradeoffs in the complexity of backdoor detection. In C. Bessiere, editor, CP'07, volume 4741 of Lecture Notes in Computer Science, pages 256--270. Springer, 2007.
• 5: Gecode Team. Gecode: Generic constraint development environment, 2006. Available from http://www.gecode.org.
• 6: M. Z. Lagerkvist and C. Schulte. Advisors for incremental propagation. In C. Bessiere, editor, CP'07, volume 4741 of Lecture Notes in Computer Science, pages 409--422. Springer, 2007.
• 7: Richard Ostrowski , Éric Grégoire , Bertrand Mazure , Lakhdar Sais, Recovering and Exploiting Structural Knowledge from CNF Formulas, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.185-199, September 09-13, 2002
• 8: P. Refalo. Impact-based search strategies for constraint programming. In CP'04, volume 3258 of Lecture Notes in Computer Science, pages 557--571. Springer, 2004.
• 9: D. Sabin and E. C. Freuder. Contradicting conventional wisdom in constraint satisfaction. In ECAI, pages 125--129, 1994.
• 10: C. Schulte and M. Carlsson. Finite domain constraint programming systems. In F. Rossi, P. van Beek, and T. Walsh, editors, Handbook of Constraint Programming, Foundations of Artificial Intelligence, chapter 14, pages 495--526. Elsevier Science Publishers, 2006.
• 11: R. Williams, C. P. Gomes, and B. Selman. Backdoors to typical case complexity. In IJCAI, pages 1173--1178, 2003.

INDEX TERMS

Keywords:
constraint programming, constraint satisfaction problems, functional dependencies, tree-search