# Experimental Evaluation Of Branching Schemes For The Csp

Thanasis Balafoutis1, Anastasia Paparrizou2**, and Kostas Stergiou**2 1 **Department of Information and Communication Systems Engineering,**
University of the Aegean, Greece.

2 **Department of Informatics and Telecommunications Engineering,**
University of Western Macedonia, Greece.

Abstract. **The search strategy of a CP solver is determined by the**
variable and value ordering heuristics it employs and by the **branching**
scheme it follows. Although the effects of variable and value **ordering**
heuristics on search effort have been widely studied, the effects of different branching schemes have received less attention. In this paper we study this effect through an experimental evaluation that includes standard branching schemes such as 2-way, d**-way, and dichotomic domain**
splitting, as well as variations of set branching where branching is performed on sets of values. We also propose and evaluate a generic approach to set branching where the partition of a domain into sets is created using the scores assigned to values by a value ordering heuristic, and a clustering algorithm from machine learning. Experimental results **demonstrate** that although exponential differences between branching schemes, as predicted in theory between 2-way d**-way branching, are not very common,**
still the choice of branching scheme can make quite a difference on certain classes of problems. Set branching methods are very competitive with 2-way branching and outperform it on some problem classes. A statistical analysis of the results reveals that our generic clustering-based set branching method is the best among the methods compared.

## 1 Introduction

Complete algorithms for CSPs are based on exhaustive backtracking search interleaved with constraint propagation. Search is typically guided by **variable and**
value ordering heuristics and makes use of a specific branching scheme like 2way or d**-way branching. Although the impact of variable and value ordering**
heuristics on search performance are topics that have received very wide attention from the early days of CP, the impact of different branching schemes has not been as widely studied. As a result, the majority of modern finite **domain** CP solvers offer a wide range of variable and value ordering heuristics **for the**
user/modeller to choose from, but at the same time they typically always employ 2-way branching. Some solvers allow for the user to implement different branching schemes, but it is not clear in which cases this may be desirable, and which particular scheme should be prefered.