approach, values that are "tied" according to their value ordering **heuristic score**
are grouped together and branching is performed on the sets of values created. Assignment of specific values to variables is postponed until lower levels of the search tree (which is also done in Larossa's method). Experiments using both depth-first search and limited discrepancy search displayed promising results.

However, this method relies heavily on the particular value ordering heuristic used and the number of ties produced by the value ordering heuristic, which can be quite low in many cases. Also, this method distinguishes between values that have very close but not equal scores and as a result such values will **be placed** into different sets. As noted in [17], the concept of a tie can be extended to refer to values having close scores. In this paper we explore this idea further.

## 3.2 Clustering For Set Branching

As we intend to apply set branching dynamically throughout search, after selecting a variable x with current domain D(x) = {a1, . . . , ad}**, we are faced with the**
following problem. We have to create a partition SD(x) = {s1**, . . . , s**m} of D(x)
into m sets s.t. each value ai ∈ D(x) belongs to only one set sj ∈ S**. Ideally,**
we want all the values that have been assigned to a specific set to be **similar** according to some measure of similarity.

Following van Hoeve and Milano, we use a generic measure of similarity that is based on the score of the values according to a value ordering heuristic. In order to perform the dynamic partitioning of domains into sets, we propose the use of clustering algorithms from machine learning. Our approach can be summarized as follows. A value ordering heuristic is used to assign a score vi **to each value** ai ∈ D(x). The collection of d **items (values) and the matrix of their scores are**
given as input to a clustering algorithm. The output of the algorithm will be the partition SD(x) = {s1**, . . . , s**m}.

Compared to [17] our approach has the following potential benefits. First, not only will tied values be placed in the same set, but with high probability so will values that have very close scores. Hence, there will be fewer sets, resulting in lower branching factor. Second, in cases where there are no ties, the method of [17] uses d**-way branching. In contrast, our approach will still partition the** domain if there are groups of values with similar score.

The algorithm we currently use to create the clustering of values is **x-means**
[12]. This is an extension of the well known k-means algorithm that is considerably faster and does not require to predetermine the desired number of clusters.

The algorithm starts with randomly selected points (values in our case) as cluster centroids and iteratively improves the computed clustering until a fixpoint is reached. Several parameters of the algorithm can be tuned to give more accurate results on a specific application, including the starting centroids, the number of iterations, the measure of distance between points, etc. Although we intend to investigate this in the future, in the experiments reported below we **use the Weka** implementation of the x-means algorithm as is, without any tuning.