License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2021.9
URN: urn:nbn:de:0030-drops-153002
URL: https://drops.dagstuhl.de/opus/volltexte/2021/15300/
Go to the corresponding LIPIcs Volume Portal


Li, Hongbo ; Yin, Minghao ; Li, Zhanshan

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

pdf-format:
LIPIcs-CP-2021-9.pdf (0.6 MB)


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.

BibTeX - Entry

@InProceedings{li_et_al:LIPIcs.CP.2021.9,
  author =	{Li, Hongbo and Yin, Minghao and Li, Zhanshan},
  title =	{{Failure Based Variable Ordering Heuristics for Solving CSPs}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{9:1--9:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15300},
  URN =		{urn:nbn:de:0030-drops-153002},
  doi =		{10.4230/LIPIcs.CP.2021.9},
  annote =	{Keywords: Constraint Satisfaction Problem, Variable Ordering Heuristic, Failure Rate, Failure Length}
}

Keywords: Constraint Satisfaction Problem, Variable Ordering Heuristic, Failure Rate, Failure Length
Collection: 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Issue Date: 2021
Date of publication: 15.10.2021
Supplementary Material: Software (Source Code): https://github.com/lihb905/fbs/ archived at: https://archive.softwareheritage.org/swh:1:dir:2c2d84dba840b8f5299bf2bc2edc8df70031c82a


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI