Finite Domain Constraint Solver Learning

1 Introduction

Constraint Satisfaction Problems (or CSPs) have been widely recognized as a powerful tool to model, formulate and solve artificial intelligence problems as well as industrial ones. A common framework to address this task is the combination of search and filtering by a local consistency. Enforcing a local consistency is usually done by the scheduling of monotonic and contracting operators up to reach their greatest common fix point. The consistency is obtained as the common closure of the set of operators. This closure is efficiently computed by a chaotic iteration of the operators [Apt, 1999]. But usually, the task of finding efficient operators which actually define a consistency is considered as one of the smartest skills of the solver's implementor. The essence of the learning framework consists in considering the behavior of the operator enforcing the desired consistency as a set of examples in order to find an adequate representation of this operator in a given language.

2 Theoretical framework

Let V be a set of variables and D = ( D x) x E v their finite domains. A constraint cis a pair (W, T) where W ~ V is the arity of the constraints and T ~ TixEW D xis the set of solu­ tions of c. A CSP is a set of constraints. For W ~ V, a search states is a tuple (sx hEw where VX E W, sx ~ Dx. A sing letonic search state ( { v x}) x E w represents a single tu­ ple. ThesearchspaceisSw = TixEwP(Dx). ThesetSw ordered by point-wise inclusion ~ forms a complete lattice. A consistency for a constraint c = (W, T) is an operator

f : Sw ---+ Sw such that:

• f is monotonic, i.e s ~ s' => f(s) ~ f(s'), in order to ensure the confluence of the reduction mechanism,
• f is contracting, i.e Vs E Sw, f(s) ~ s, in order to reduce variable's domains,
• f is correct w.r.t c, i.e V s E Sw, every solutions of c which are present in s remain in f ( s),
• f represents c, i.e for every singletonic search state s which does not represent a solution of c, f(s) is an empty state (at least one element of the tuple f(s) is the empty set).

Operators which satisfy the first three conditions are called pre-consistencies for c. As an example of consistency, if we suppose that each variable domain D x is ordered by a total ordering ::; and for A ~ D x, we denote by [A] the set {a E D xI min( A) ::; a ::; max( A)}, then the bound-consistency bee is defined by Vs E Sw, VX E W, bce(s)x = sx n [Tx ], with Tx the projection ofT on X.

Let cse be the consistency to be learned. Our aim is to build a consistency f which behaves like cse as much as pos­ sible. Thus f must be contracting, monotonic, correct w.r.t cse (Vs E Sw, cse(s) ~ f(s)) and singleton complete w.r.t cse (f ( s) ~ cse ( s) for any singletonic search state s ). How­ ever, singleton completeness is difficult to get and even not always possible to express in a given language. In order to transform a pre-consistency into a consistency, let us define a consistency ide such that V s E Sw, ide ( s) is an empty state if s is a non-solution singletonic state, and ide ( s) = s other­ wise. Thus f o ide and ide o f are consistencies for c iff is a pre-consistency for c. Therefore by adding ide in the set of operators, processed by a chaotic iteration mechanism [Apt, 1999], we only need to build pre-consistencies for c. On the other hand, the correctness condition must be ensured for ev­ ery s E Sw which is generally huge. We show that:

Proposition 1 Iff is a monotonic and contracting operator such that f ( s) = s for every single tonic state s which repre­ sents a solution of c, then f is a pre-consistency for c.

Therefore, by considering monotonic operators, we can re­ duce the search space to a sample set E which is a subset of Sw and which contains all singletonic search states. Let £ be the language in which operators are expressed and l be an operator in this language. In order to find the best possible ex­ pression, we shall be able to compare two consistencies. This is usually done with a distance. Let d be such a distance be­ tween two consistencies. The learning problem is formulated as follows:

minimize subject to d(cs 5 , l), \:Is E E, cse(s) s-;; l(s) s-;; s,

where E s-;; Sw, E contains all singletonic search states of Sw and l is a monotonic operator. Following the machine learning vocabulary, cse represents the example space and£ the hypothesis space.

3 Learning indexicals

To instantiate our theoretical framework, we have to define strong language biases in order to limit the combinatorial ex­ plosion.

The first question is the language in which operators are ex­ pressed. The language of indexicals [van Hentenryck et al., 1991] is chosen, motivated by the ease of integration of the user-defined indexicals in Gnu-Prolog [Diaz and Codognet, 2001]. In this language, an operator is written X in r, where X represents the domain of the variable X and r is an expression representing a subset of D x. If we denote x the unary constraint representing X's domain, then the indexical represents the operator x f-7 x n r.

Then comes the choice of consistency. We learn the bound­ consistency, since it allows to limit the example space to in­ tervals instead of arbitrary subsets.

For each variable we learn a reduction indexical and de­ fine an indexical for ide. The reduction indexical for X is of the form X in minX . . maxX where minX, maxX are in some fixed forms. In practice, we use linear, piecewise lin­ ear and rational forms. In order to the reduction indexical to be monotonic, the bound minX must be anti-monotonic and maxX monotonic. This can be ensured by syntactic condi­ tions on the sign of the coefficients for each expression.

The indexicals for ide could be implemented in two ways: by using Gnu-Prolog indexicals for predefined constraints in which each instance of min and max is simply replaced by val, or by a direct code using val and C operators.

As distance between two consistencies, we use the global error on the example space E. By considering that f must be correct w.r.t cse, this distance is ~sEEJ/(s)\cse(s)J.

Example For lack of space, we present here one example. An user defined global constraint is defined by the follow­ ing conjunction: X- Y > 3,X- Y < 30,3 *X- Y > 50, 5 * Y - X < 120, X < 45, Y > 5. When treated glob­ ally as a two dimensional polyhedra, these constraints yield less indexicals than the above decomposition. On the domain [0 .. 49] x [0 .. 49], our system generates the following opera­ tors:

X in 6*min(Y)/<20+18 .. -10/<(1 + max(Y))+45 Yin 10/<(max(X)+1)+6 .. -590/<(max(X)+1)+47 Reparation operators are implemented from Gnu-Prolog in­

dexicals. Here is the one for X:

X in val(Y)+4 . . 44 & 0 . . val(Y)+29 & 50+val(Y)/>3+1 .. 44 & S*val(Y)-119 .. 44

When trying all reductions on boxes included in [16, 25] x [5, 26], the learned operators ran in 290 ms, while the non­ decomposed constraints ran in 400 ms. All tests have been done on a Pentium4, 2Ghz, 512MB running Linux.

4 Conclusion

Related work Solver learning has been firsr introduced by [Apt and Monfroy, 1999] in which they automatically gener­ ate a set of rules from the tuples defining a constraint. The complexity of the rules generation limits them to small finite domains such as boolean.

The system PROP MINER [Abdennadher and Rigotti , 2002; 2003] is devoted to the learning of Constraint Handling Rules [Friiwirth, 1998]. The produced solver is often very readable, especially when a small number of rules are produced. While being less general in theory since we only deal with finite domains, our method works on domains and constraint arities much larger.

In an earlier paper [Dao et al., 2002], we have presented an indexical learning process. We propose here two main im­ provements, besides a more general theoretical framework: the possibility of using only a sample of the example space while still ensuring the correctness of the learned solver and the reparation method. It follows that our system is able to handle larger constraint arity and larger domains and there­ fore yields a better solver.

Summary We have presented a general, language­ independent framework for finite domain constraint solver learning and an instantiation to the learning of bound­ consistency with Gnu-Prolog indexicals.

Acknowledgment We gratefully thank Michel Bergere and the anonymous referees for their remarks on this paper. This work is supported by french CNRS grant 2JE095.