# Using Machine Learning To Make Constraint Solver Implementation Decisions

Lars Kotthof f, Ian Gent, and Ian Miguel
{larsko,ipg,ianm}@cs.st-andrews.ac.uk University of St Andrews Abstract. Programs to solve so-called constraint problems are complex pieces of software which require many design decisions to be made more or less arbitrarily by the implementer. These decisions affect the performance of the finished solver significantly [13]. Once a design decision has been made, it cannot easily be reversed, although a different decision may be more appropriate for a particular problem.

We investigate using machine learning to make these decisions automatically depending on the problem to solve with the alldifferent constraint as an example. Our system is capable of making non-trivial, multi-level decisions that improve over always making a default choice.

## 1 Introduction

Constraints are a natural, powerful means of representing and reasoning about combinatorial problems that impact all of our lives. Constraint solving is applied successfully in a wide variety of disciplines such as aviation, industrial design, banking, combinatorics and the chemical and steel industries, to name but a few examples. A *constraint satisfaction problem* (CSP [3]) is a set of decision variables, each with an associated domain of potential values, and a set of constraints. An assignment maps a variable to a value from its domain. Each constraint specifies allowed combinations of assignments of values to a subset of the variables. A *solution* to a CSP is an assignment to all the variables that satisfies all the constraints. Solutions are typically found for CSPs through systematic search of possible assignments to variables. During search, constraint *propagation* algorithms are used. These propagators make inferences, usually recorded as domain reductions, based on the domains of the variables constrained and the assignments that satisfy the constraints. If at any point these inferences result in any variable having an empty domain then search backtracks and a new branch is considered.

When implementing constraint solvers and modelling constraint problems, many design decision have to be made - for example how much propagation to do, what data structures to use to enable the solver to backtrack and when and how often to check if a constraint is satisfied and which values could be removed. These decisions have so far been made mostly manually. Making the
"right" decision often depends on the experience of the person making it.