On combining variable ordering heuristics for constraint satisfaction problems

摘要

Variable ordering heuristics play a central role in solving constraint satisfaction problems. Combining two variable ordering heuristics may generate a more efficient heuristic, such as dom/deg. In this paper, we propose a novel method for combining two variable ordering heuristics, namely Pearson-Correlation-Coefficient-based Combination (PCCC). While the existing combination strategies always combine participant heuristics, PCCC checks whether the participant heuristics are suitable for combination before combining them in the context of search. If they should be combined, it combines the heuristic scores to select a variable to branch on, otherwise, it randomly selects one of the participant heuristics to make the decision. The experiments on various benchmark problems show that PCCC can be used to combine different pairs of heuristics, and it is more robust than the participant heuristics and some classical combining strategies.