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

Hongbo Li, Yanchun Liang, Ning Zhang, Jinsong Guo, Dong Xu and Zhanshan Li ()
Additional contact information
Hongbo Li: Jilin University
Yanchun Liang: Jilin University
Ning Zhang: University of Missouri
Jinsong Guo: University of Oxford
Dong Xu: University of Missouri
Zhanshan Li: Jilin University

Journal of Heuristics, 2016, vol. 22, issue 2, No 1, 125-145

Abstract: Abstract In this paper, we improved two classical degree-based variable ordering heuristics, $$\frac{\textit{Dom}}{\textit{Ddeg}}$$ Dom Ddeg and $$\frac{\textit{Dom}}{\textit{Wdeg}}$$ Dom 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.

Keywords: Constraint satisfaction problem; Variable ordering heuristic; Weighted degree; Constraint tightness (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-015-9305-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:22:y:2016:i:2:d:10.1007_s10732-015-9305-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-015-9305-2

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().