Branching Schemes and Variable Ordering Heuristics for Constraint Satisfaction Problems: Is There Something to Learn?

When solving a constraint satisfaction problem by using systematic algorithms it is needed to expand and explore a search tree to find a solution. In this work we study both binary and k-way branching schemes while they interact with various variable ordering heuristics, and how those interactions affect the cost of finding a solution to different instances. Both branching schemes have been used in previous investigations and it is not straight forward to determine the conditions that make one branching scheme better than the other. But we provide evidence that, in order to decide, variable ordering heuristics play a major role in the performance of these branching schemes. This study is intended to work as a preliminary study to develop hyper-heuristics for branching schemes in combination with variable ordering heuristics. The final part of the analysis presents a very simple naive hyper-heuristic that randomly applies binary and k-way branching as the search progresses in combination with some well known variable ordering heuristics. The scope of this paper is to explore the interactions between different variable ordering heuristics and these two branching schemes, in order to produce some relations between their performance. We expect these relations to be used in further studies as the basis for more robust hyper-heuristics that take into consideration the information gathered in this investigation.