Document Open Access Logo

Failure Based Variable Ordering Heuristics for Solving CSPs (Short Paper)

Authors Hongbo Li , Minghao Yin, Zhanshan Li

PDF
Thumbnail PDF

File

LIPIcs.CP.2021.9.pdf
  • Filesize: 0.62 MB
  • 10 pages

Document Identifiers

Author Details

Hongbo Li
  • School of Information Science and Technology, Northeast Normal University, Changchun, China
Minghao Yin
  • School of Information Science and Technology, Northeast Normal University, Changchun, China
Zhanshan Li
  • College of Computer Science and Technology, Jilin University, Changchun, China

Funding

  • Li, Hongbo: The National Natural Science Foundation of China under Grant NO. 61802056.
  • Yin, Minghao: The National Natural Science Foundation of China under Grant NO. 61976050.
  • Li, Zhanshan: Open Research Fund of Key Laboratory of Space Utilization, Chinese Academy of Sciences under Grant NO. LSU-KFJJ-2019-08.

Cite AsGet BibTex

Hongbo Li, Minghao Yin, and Zhanshan Li. Failure Based Variable Ordering Heuristics for Solving CSPs (Short Paper). In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 9:1-9:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CP.2021.9

Abstract

Variable ordering heuristics play a central role in solving constraint satisfaction problems. In this paper, we propose failure based variable ordering heuristics. Following the fail first principle, the new heuristics use two aspects of failure information collected during search. The failure rate heuristics consider the failure proportion after the propagations of assignments of variables and the failure length heuristics consider the length of failures, which is the number of fixed variables composing a failure. We performed a vast experiments in 41 problems with 1876 MiniZinc instances. The results show that the failure based heuristics outperform the existing ones including activity-based search, conflict history search, the refined weighted degree and correlation-based search. They can be new candidates of general purpose variable ordering heuristics for black-box CSP solvers.

Subject Classification

ACM Subject Classification
  • Computing methodologies
Keywords
  • Constraint Satisfaction Problem
  • Variable Ordering Heuristic
  • Failure Rate
  • Failure Length

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. C. Bessière and J. C. Règin. Mac and combined heuristics: two reasons to forsake fc (and cbj?) on hard problems. In Proc. CP'96, pages 61-75. Springer, 1996. Google Scholar
  2. F. Boussemart, F. Hemery, C. Lecoutre, and L. Sais. Boosting systematic search by weighting constraints. In Proc. ECAI'04, pages 146-150, 2004. Google Scholar
  3. 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 Proc. CP'96, pages 179-193. Springer, 1996. Google Scholar
  4. C. P. Gomes, B. Selman, and H. Kautz. Boosting combinatorial search through randomization. In Proc. AAAI'98, pages 431-437. AAAI, 1998. Google Scholar
  5. D. Habet and C. Terrioux. Conflict history based search for constraint satisfaction problem. In Proc. of the 34th ACM/SIGAPP Symposium on Applied Computing, pages 1117-1122. ACM, 2019. Google Scholar
  6. R. Haralick and G. Elliott. Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14:263-313, 1980. Google Scholar
  7. E. Hebrard and M. Siala. Explanation-based weighted degree. In Proc. CPAIOR'17, pages 167-175. Springer, 2017. Google Scholar
  8. J. Hwang and D. G. Mitchell. 2-way vs d-way branching for csp. In Proc. CP'05, pages 343-357. Springer, 2005. Google Scholar
  9. C. Lecoutre, L. Saïs, S. Tabary, and V. Vidal. Reasoning from last conflict(s) in constraint programming. Artificial Intelligence, 173(18):1592-1614, 2009. Google Scholar
  10. H. Li, Y. Liang, N. Zhang, J. Guo, D. Xu, and Z. Li. Improving degree-based variable ordering heuristics for solving constraint satisfaction problems. Journal of Heuristics, 22(2):125-145, 2016. Google Scholar
  11. P. Liberatore. On the complexity of choosing the branching literal in dpll. Artificial Intelligence, 116(1):315-326, 2000. Google Scholar
  12. L. Michel and P. Van Hentenryck. Activity-based search for black-box constraint programming solvers. In Proc. CPAIOR'12, pages 228-243. Springer, 2012. Google Scholar
  13. G. Pesant, C. G. Quimper, and A. Zanarini. Counting-based search: Branching heuristics for constraint satisfaction problems. Journal of Artificial Intelligence Research, 43:173-210, 2012. Google Scholar
  14. C. Prud'homme, J-G. Fages, and X. Lorca. Choco Documentation. TASC - LS2N CNRS UMR 6241, COSLING S.A.S., 2017. URL: http://www.choco-solver.org.
  15. P. Refalo. Impact-based search strategies for constraint programming. In Proc. CP'04, pages 557-571. Springer, 2004. Google Scholar
  16. B. M. Smith and S. A. Grant. Trying harder to fail first. In Proc. ECAI'98, pages 249-253, 1998. Google Scholar
  17. T. Walsh. Search in a small world. In Proc. IJCAI'99, pages 1172-1177, 1999. Google Scholar
  18. R. Wang, W. Xia, and R. H. C. Yap. Correlation heuristics for constraint programming. In Proc. ICTAI'17, pages 1037-1041. IEEE, 2017. Google Scholar
  19. H. Wattez, F. Koriche, C. Lecoutre, A. Paparrizou, and S. Tabary. Learning variable ordering heuristics with multi-armed bandits and restarts. In Proc. ECAI'20, pages 371-378. IOS Press, 2020. Google Scholar
  20. H. Wattez, C. Lecoutre, A. Paparrizou, and S. Tabary. Refining constraint weighting. In Proc. of ICTAI'19, pages 71-77. IEEE, 2019. Google Scholar
  21. W. Xia and R. H. C. Yap. Learning robust search strategies using a bandit-based approach. In Proc. AAAI'18, pages 6657-6665. AAAI, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact