Tightness The tightness of a constraint is the proportion of disallowed tuples.

The tightness is estimated by sampling 1000 random tuples (that are valid w.r.t. variable domains) and testing if the tuple satisfies the constraint. The tightness quartiles and the mean tightness over all constraints is used.

Proportion of symmetric variables In many CSPs, the variables form equivalence classes where the number and type of constraints a variable is in are the same. For example in the CSP x1 × x2 = x3, x4 × x5 = x6, x1, x2, x4, x5 are all indistinguishable, as are x3 and x6. The first stage of the algorithm used by Nauty [17] detects this property. Given a partition of n variables generated by this algorithm, we transform this into a number between 0 and 1 by taking the proportion of all pairs of variables which are in the same part of the partition.

Alldifferent statistics The size of the union of all variables in an alldifferent constraint divided by the number of variables. This is a measure of how many assignments to all variables that satisfy the constraint there are. We used the quartiles and the mean over all alldifferent constraints.

In creating this set of attributes, we intended to cover a wide range of possible factors that affect the performance of different alldifferent implementations.

Wherever possible, we normalised attributes that would be specific to problem instances of a particular size. This is based on the intuition that similar instances of different sizes are likely to behave similarly. Computing the features took 27 seconds per instance on average.

## 5 Learning A Problem Classifier

Before we used machine learning on the set of training instances, we annotated each problem instance with the alldifferent implementation that had the best performance on it according to the following criteria. If the na¨ıve alldifferent implementation took less CPU time than all the other ones, it was chosen, else the implementation which had the best performance in terms of search nodes per second was chosen. As all implementations except the na¨ıve one explore the same search space, nodes per second is a more reliable measure of performance than only CPU time. If no solver was able to solve the instance, we assigned a
"don't know" annotation.

We used the WEKA [10] machine learning software through the R interface to learn classifiers. We used almost all of the WEKA classifiers that were applicable to our problem - algorithms which generate decision rules, decision trees, Bayesian classifiers, nearest neighbour and neural networks. Our selection is broad and includes all major machine learning methodologies. The specific classifiers we used are BayesNet, BFTree, ConjunctiveRule, DecisionTable, FT, HyperPipes, IBk, J48, J48graft, JRip, LADTree, MultilayerPerceptron, NBTree, OneR, PART, RandomForest, RandomTree, REPTree and ZeroR, all of which are described in [22].

The problem of classifying problem instances here is different to normal machine learning classification problems. We do not particularly care about classi-