We approach this problem using machine learning. Given a particular problem, we want to decide *automatically* which design decisions to make. This improves over the current state of the art in two ways. First, we do not require humans to more or less arbitrarily decide on something they may not have any experience with. Second, we can change design decisions for particular problems.

We demonstrate that we can approach machine learning as a "black box" and use generic techniques to increase the performance of the learned classifiers. The result is a system which is able to dynamically decide which implementation to use by looking at an unknown problem. The decision made is in general better than simply relying on a default choice and enables us to solve constraint problems faster.

## 2 Background

We are addressing an instance of the Algorithm Selection Problem [21], which, given variable performance among a set of algorithms, is to choose the best candidate for a particular problem instance. Machine learning is an established method of addressing this problem [14, 16]. Particularly relevant to our work are the machine learning approaches that have been taken to configure, to select among, and to tune the parameters of solvers in the related fields of mathematical programming, propositional satisfiability (SAT), and constraints.

Multi-tac [18] configures a constraint solver for a particular instance distribution. It makes informed choices about aspects of the solver such as the search heuristic and the level of constraint propagation. The Adaptive Constraint Engine [4] learns search heuristics from training instances. SATenstein [12] configures stochastic local search solvers for solving SAT problems.

An algorithm *portfolio* consists of a collection of algorithms, which can be selected and applied in parallel to an instance, or in some (possibly truncated) sequence. This approach has recently been used with great success in SATzilla [23]
and CP Hydra [19]. In earlier work Borrett *et al* [2] employed a sequential portfolio of constraint solvers. Guerri and Milano [9] use a decision-tree based technique to select among a portfolio of constraint- and integer-programming based solution methods for the bid evaluation problem. Similarly, Gent *et al* [5] investigate decision trees to choose whether to use lazy constraint learning [7] or not.

Rather than select among a number of algorithms, it is also possible to learn parameter settings for a particular algorithm. Hutter *et al* [11] apply this method to local search. Ansotegui *et al* [1] employ a genetic algorithm to tune the parameters of both local and systematic SAT solvers.

The *alldifferent* constraint requires all variables which it is imposed on to be pairwise alldifferent. For example alldiff(x1, x2, x3) enforces x1 6= x2, x1 6= x3 and x2 6= x3.

There are many different ways to implement the alldifferent constraint. The na¨ıve version decomposes the constraint and enforces disequality on each pair of variables. More sophisticated versions (e.g. [20]) consider the constraint as a whole and are able to do more propagation. For example an alldifferent constraint