2-way d**-way, are not very common. But although the choice of branching scheme**
does not have as a profound effect as the choice of variable ordering heuristic, it can still make a difference. The generic set branching methods we evaluate outperform the standard 2-way branching scheme in many problem classes resulting in better average performance. It is notable that our clustering-based set branching method displays very promising results without any tuning of the clustering algorithm applied. Importantly, a statistical analysis of the experimental results reveals that this method is the best among the methods compared.

The rest of the paper is organized as follows. Section 2 gives necessary background. In Section 3 we discuss past work on set branching for CSPs and propose a new generic method for set branching. In Section 4 we report results from an experimental evaluation of the various branching schemes including **a statistical** analysis. Finally, in Section 5 we conclude.

## 2 Background

A Constraint Satisfaction Problem (CSP) is a tuple (X, D, C), where X **is a set**
containing n variables {x1, x2, ..., xn}; D is a set of domains {D(x1), D(x2)**,...,**
D(xn)} for those variables, with each D(xi**) consisting of the possible values**
which xi may take; and C is a set of constraints {c1, c2, ..., ce} **between variables**
in subsets of X. Each constraint c ∈ C expresses a relation rel(c**) defining the** variable assignment combinations that are allowed for the variables in **the scope**
of the constraint **vars(**c).

Complete search algorithms for CSPs are typically based on backtracking depth-first search where branching decisions (e.g. variable assignments) are interleaved with constraint propagation. Search is guided by variable **ordering**
heuristics and value ordering heuristics.

One of the most efficient general purpose variable ordering heuristics that have been proposed is dom/wdeg **[3]. This heuristic assigns a weight to each** constraint, initially set to one. Each time a constraint causes a conflict, i.e. a domain wipeout, its weight is incremented by one. Each variable is associated with a weighted degree**, which is the sum of the weights over all constraints** involving the variable and at least another unassigned variable. The **dom/wdeg**
heuristic chooses the variable with minimum ratio of current domain size to weighted degree.

A well-known generic value ordering heuristic for binary CSPs is Geelen's promise [6]. For each value a ∈ D(x**) this heuristic counts the number of values**
that are compatible with a in each future unassigned variable that x is constrained with. The product of these counts is the promise of a**. The value with**
the maximum promise is selected.

## 3 Branching Schemes

From the early days of CSP research, search algorithms were usually implemented using either a d-way or a 2-way branching scheme. The former works