Evaluating and Improving Modern Variable and Revision Ordering Strategies in CSPs

• Autorzy: Balafoutis T. , Stergiou K.
• Języki publikacji: EN

Abstrakty

EN

A key factor that can dramatically reduce the search space during constraint solving is the criterion under which the variable to be instantiated next is selected. For this purpose numerous heuristics have been proposed. Some of the best of such heuristics exploit information about failures gathered throughout search and recorded in the form of constraint weights, while others measure the importance of variable assignments in reducing the search space. In this work we experimentally evaluate the most recent and powerful variable ordering heuristics, and new variants of them, over a wide range of benchmarks. Results demonstrate that heuristics based on failures are in general more efficient. Based on this, we then derive new revision ordering heuristics that exploit recorded failures to efficiently order the propagation list when arc consistency is maintained during search. Interestingly, in addition to reducing the number of constraint checks and list operations, these heuristics are also able to cut down the size of the explored search tree.

Słowa kluczowe

EN

constraint satisfaction problems; search heuristics; variable ordering; revision ordering

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 102, nr 3/4
• Strony: 229--261
• Opis fizyczny: Bibliogr. 42 poz., tab.

Twórcy

autor

Balafoutis T.

autor

Stergiou K.

• Department of Information & Communication Systems Engineering, University of the Aegean, Karlovassi, Samos, 83200, Greece,

Bibliografia

• [1] T. Balafoutis and K. Stergiou. Experimental evaluation of modern variable selection strategies in constraint satisfaction problems. In Proceedings of the 15th RCRA workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion. Volume 451 of CEUR Workshop Proceedings., (CEURWS. org), 2008.
• [2] T. Balafoutis and K. Stergiou. Conflict directed variable selection strategies for constraint satisfaction problems. In Proceedings of the 6th Hellenic Conference on Artificial Intelligence (SETN 2010), LNAI 6040, pages 29-38, 2010.
• [3] C. Bessière, A. Chmeiss, and L. Sais. Neighborhood-based variable ordering heuristics for the contraint satisfaction problem. In Proceedings of the 7th Conference on Principles and Practice of Constraint Programming (CP-2001), pages 61-75, 2001.
• [4] C. Bessière, E.C. Freuder, and J.C. Régin. Using Inference to Reduce Arc Consistency Computation. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-1995), pages 592-599, 1995.
• [5] C. Bessière and J.C. Régin. MAC and combined heuristics: two reasons to forsake FC (and CBJ?). In Proceedings of the 2nd Conference on Principles and Practice of Constraint Programming (CP-1996), pages 61-75, Cambridge MA, 1996.
• [6] C. Bessière, J.C. Régin, R. Yap, and Y. Zhang. An Optimal Coarse-grained Arc Consistency Algorithm. Artificial Intelligence, 165(2):165-185, 2005.
• [7] F. Boussemart, F. Hemery, and C. Lecoutre. Revision ordering heuristics for the Constraint Satisfaction Problem. In 10th International Conference on Principles and Practice of Constraint Programming (CP-2004), Workshop on Constraint Propagation and Implementation, Toronto, Canada, 2004.
• [8] F. Boussemart, F. Hemery, C. Lecoutre, and L. Sais. Boosting systematic search by weighting constraints. In Proceedings of 16th European Conference on Artificial Intelligence (ECAI-2004), pages 146-150, Valencia, Spain, 2004.
• [9] D. Brelaz. New methods to color the vertices of a graph. Communications of the ACM, 22:251-256, 1979.
• [10] B. Cabon, S. De Givry, L. Lobjois, T. Schiex, and J.P. Warners. Radio Link Frequency Assignment. Constraints, 4:79-89, 1999.
• [11] H. Cambazard and N. Jussien. Identifying and Exploiting Problem Structures Using Explanation-based Constraint Programming. Constraints, 11:295-313, 2006.
• [12] A. Chmeiss and P. Jégou. Efficient path-consistency propagation. Journal on Artificial Intelligence Tools, 7(2):121-142, 1998.
• [13] M. Correia and P. Barahona. On the integration of singleton consistency and look-ahead heuristics. In Proceedings of the ERCIM workshop - CSCLP, pages 47-60, 2007.
• [14] R. Debruyne and C. Bessière. Domain Filtering Consistencies. Journal of Artificial Intelligence Research, 14:205-230, 2001.
• [15] R. Dechter and I. Meiri. Experimental evaluation of preprocessing techniques in constraint satisfaction problems. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-1989), pages 271-277, 1989.
• [16] M. van Dongen. AC-3d an efficient arc-consistency algorithm with a low space-complexity. In Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming (CP-2002), volume 2470, pages 755-760, 2002.
• [17] E.C. Freuder. A sufficient condition for backtrack-free search. Journal of the ACM, 29(1):24-32, 1982.
• [18] D. Frost and R. Dechter. Look-ahead value ordering for constraint satisfaction problems. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-1995), pages 572-578, 1995.
• [19] I.P. Gent, E. MacIntyre, P. Prosser, P. Shaw, and T. Walsh. The constraindedness of arc cosistency. In Proceedings of the 3rd Conference on Principles and Practice of Constraint Programming (CP-1997), pages 327-340, 1997.
• [20] I.P Gent, E. MacIntyre, P. Prosser, B.M. Smith, and T. Walsh. An empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem. In Proceedings of the 2nd Conference on Principles and Practice of Constraint Programming (CP-1996), pages 179-193, 1996.
• [21] D. Grimes and R.J. Wallace. Sampling strategies and variable selection in weighted degree heuristics. In Proceedings of the 13th Conference on Principles and Practice of Constraint Programming (CP-2007), pages 831-838, 2007.
• [22] R.M. Haralick and Elliott. Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14:263-314, 1980.
• [23] F. Laburthe and N. Jussien. Choco constraint programming system. Available at http://choco.sourceforge.net, 2003-2009.
• [24] C. Lecoutre and S. Tabary. Abscon 109: a generic csp solver. In Proceedings of the 2nd International CSP Solver Competition, held with CP-2006, pages 55-63, 2008.
• [25] A. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99-118, 1977.
• [26] A. Mackworth. On reading sketch maps. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-1977), pages 598-606, Cambridge MA, 1977.
• [27] J.J. McGregor. Relational consistency algorithms anf their applications in finding subgraph and graph isomorphism. Information Science, 19:229-250, 1979.
• [28] R. Mohr and T. Henderson. Arc and Path Consistency Revisited. Artificial Intelligence, 28:225-233, 1986.
• [29] M. Moskewicz, C. Madigan, and S. Malik. Chaff: Engineering an efficient sat solver. In Proceedings of Design Automation Conference, pages 530-535, 2001.
• [30] P. Prosser, K. Stergiou, and T. Walsh. Singleton consistencies. In Proceedings of the 6th Conference on Principles and Practice of Constraint Programming (CP-2000), pages 353-368, 2000.
• [31] P. Refalo. Impact-based search strategies for constraint programming. In Proceedings of the 10th Conference on Principles and Practice of Constraint Programming (CP-2004), pages 556-571, 2004.
• [32] O. Roussel and C. Lecoutre. Xml representation of constraint networks: Format xcsp 2.1. In CoRR abs/0902.2362, 2009.
• [33] D. Sabin and E.C. Freuder. Contradicting conventional wisdom in constraint satisfaction. In Proceedings 2nd Workshop on Principles and Practice of Constraint Programming (CP-1994), pages 10-20, 1994.
• [34] C. Schulte and P.J. Stuckey. Efficient constraint propagation engines. ACM Transactions on Programming Languages and Systems, 31:2.1-2.43, 2008.
• [35] B.M. Smith. The brelaz heuristic and optimal static orderings. In Proceedings of the 5th Conference on Principles and Practice of Constraint Programming (CP-1999), pages 405-418, 1999.
• [36] B.M. Smith and S.A. Grant. Trying harder to fail first. In Proceedings of 13th European Conference on Artificial Intelligence (ECAI-1998), pages 249-253, 1998.
• [37] P. van Beek. Backtracking Search Algorithms. In F. Rossi, P. van Beek, and T. Walsh, editors, Handbook of Constraint Programming, chapter 4. Elsevier, 2006.
• [38] R. Wallace and E. Freuder. Ordering heuristics for arc consistency algorithms. In AI/GI/VI, pages 163-169, Vancouver, British Columbia, Canada, 1992.
• [39] R.J.Wallace and D. Grimes. Experimental studies of variable selection strategies based on constraint weights. Journal of Algorithms, 63(1-3):114-129, 2008.
• [40] T. Walsh. Search in a small world. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-1999), pages 1172-1177, 1999.
• [41] R. Zabih. Some applications of graph bandwith to constraint satisfaction problems. In Proceedings of AAAI'90, pages 46-51, 1990.
• [42] A. Zanarini and G. Pesant. Solution counting algorithms for constraint-centered search heuristics. In Proceedings of the 13th Conference on Principles and Practice of Constraint Programming (CP-2007), pages 743-757, 2007.