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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15300/
Li, Hongbo ;
Yin, Minghao ;
Li, Zhanshan
Failure Based Variable Ordering Heuristics for Solving CSPs (Short Paper)
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}
}
