Improving degree-based variable ordering heuristics for solving constraint satisfaction problems

详细信息    查看全文

• 作者：Hongbo Li ; Yanchun Liang ; Ning Zhang ; Jinsong Guo ; Dong Xu…
• 关键词：Constraint satisfaction problem ; Variable ordering heuristic ; Weighted degree ; Constraint tightness
• 刊名：Journal of Heuristics
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：22
• 期：2
• 页码：125-145
• 全文大小：498 KB
• 参考文献：Bessière, C., Règin, J.C.: MAC and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems. In: Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming (1996)
  Bessière, C., Règin, J.C.: Arc consistency for general constraint networks: preliminary results. In: Proceedings of the 15th International Joint Conference on Artificial Intelligence, Morgan Kaufmann (1997)
  Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boosting systematic search by weighting constraints. In: Proceedings of the 16th Eureopean Conference on Artificial Intelligence (2004)
  Dechter, R., Meiri, I.: Experimental evaluation of preprocessing techniques in constraint satisfaction problems. In: Proceedings of the 11th International Joint Conference on Artificial Intelligence (1989)
  Gent, I.P., MacIntyre, E., Presser, P., Smith, B.M., Walsh, T.: An empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem. In: Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming (1996)
  Gent, I.P., MacIntyre, E., Prosser, P., Walsh, T.: The constrainedness of search. In: Proceedings of the 13th National Conference on Artificial Intelligence (1996)
  Gomes, C.P., Selman, B., Kautz, H.: Boosting combinatorial search through randomization. In: Proceedings of the 27th AAAI Conference on Artificial Intelligence (1998)
  Haralick, R.M., Elliott, G.L.: Increasing tree search efficiency for constraint satisfaction problems. Artif. Intell. 14, 263–313 (1980)CrossRef
  Hwang, J., Mitchell, D.G.: 2-way vs d-way branching for CSP. In: Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming (2005)
  Lecoutre, C.: STR2: optimized simple tabular reduction for table constraints. Constraints 16, 341–371 (2011)MathSciNet CrossRef MATH
  Lecoutre, C., Hemery, F.: A study of residual supports in arc consistency. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence (2007)
  Lecoutre, C., Vion, J.: Enforcing arc consistency using bitwise operations. Constraint Program. Lett. 2, 21–35 (2008)
  Mackworth, A.K.: Consistency in networks of relations. Artif. Intell. 8, 99–118 (1977)CrossRef MATH
  Michel, L., Hentenryck, P.V.: Activity-based search for black-box constraint programming solvers. In: Proceedings of the 9th International Conference on Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems (2012)
  Mula, W.: SSSE3: fast popcount. http://​wm.​ite.​pl/​articles/​sse-popcount.​html , last updated (2011)
  Pesant, G., Quimper, C.G., Zanarini, A.: Counting-based search: branching heuristics for constraint satisfaction problems. J. Artif. Intell. Res. 43, 173–210 (2012)MathSciNet MATH
  Refalo, P.: Impact-based search strategies for constraint programming. In: Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming (2004)
  Règin, J.C.: A filtering algorithm for constraints of difference in CSPs. In: Proceedings of the 12th National Conference on Artificial Intelligence (1994)
  Règin, J.C., Rueher, M.: A global constraint combining a sum constraint and difference constraints. In: Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming (2000)
  Sabin, D., Freuder, E.C.: Contradicting conventional wisdom in constraint satisfaction. In: Proceedings of the 11th European Conference on Artificial Intelligence (1994)
  Smith, B.M., Grant, S.A.: Trying harder to fail first. In: Proceedings of the 13th European Conference on Artificial Intelligence (1998)
  Ullmann, J.R.: Partition search for non-binary constraint satisfaction. Inf. Sci. 177, 3639–3678 (2007)MathSciNet CrossRef MATH
  Walsh, T.: Search in a Small World. In: Proceedings of the 16th International Joint Conference on Artificial Intelligence (1999)
  Xu, K., Boussemart, F., Hemery, F., Lecoutre, C.: Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artif. Intell. 171, 514–534 (2007)MathSciNet CrossRef MATH
  Xu, K., Li, W.: Exact phase transitions in random constraint satisfaction problems. J. Artif. Intell. Res. 12, 93–103 (2000)MathSciNet MATH
  
• 作者单位：Hongbo Li (1) (2)
  Yanchun Liang (1)
  Ning Zhang (4)
  Jinsong Guo (3)
  Dong Xu (4)
  Zhanshan Li (1)
  
  1. Key Laboratory for Symbol Computation and Knowledge Engineering of National Education Ministry, College of Computer Science and Technology, Jilin University, Changchun, 130012, China
  2. School of Computer Science and Information Technology, Northeast Normal University, Changchun, 130117, China
  4. Department of Computer Science and Christopher S. Bond Life Sciences Center, University of Missouri, Columbia, MO, 65211, USA
  3. Department of Computer Science, University of Oxford, Oxford, UK
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Operations Research and Mathematical Programming
  Operation Research and Decision Theory
  Artificial Intelligence and Robotics
  Calculus of Variations and Optimal Control
  
• 出版者：Springer Netherlands
• ISSN：1572-9397

文摘

In this paper, we improved two classical degree-based variable ordering heuristics, \(\frac{\textit{Dom}}{\textit{Ddeg}}\) and \(\frac{\textit{Dom}}{\textit{Wdeg}}\). We propose a method using the summation of constraint tightness in degree-based heuristics. We also propose two methods to calculate dynamic constraint tightness for binary extensional constraints and non-binary intensional constraints respectively. Our work shows how constraint tightness can be practically used to guide search. We performed a number of experiments on some benchmark instances. The results have shown that, the new heuristics improve the classical ones by both computational time and search tree nodes and they are more efficient than some other successful heuristics on the instances where the classical heuristics work well.