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

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.