Propagate the Right Thing: How Preferences Can Speed-Up Constraint Solving

1 Introduction

In the last two decades, considerable research effort in AI has been spent on studying the complexity of reasoning and problem solving, and the identification of tractable cases has become an important goal of this research. However, even if a problem can be solved by a polynomial algorithm, or if search effort can be reduced by polynomial algorithms, this might not be sufficient for real-world AI systems that face challenges such as interactivity and real-time. We give some examples from constraint satisfaction, where achieving arc consistency might be too costly, although it is tractable:

1. Web-based configuration systems must provide a re­ sponse in a few seconds while serving multiple users. Although arc consistency (AC) is an appropriate tech­ nique to handle compatibility constraints, it will be too expensive in presence of large product catalogs.
2. Constraint-based approaches to problems such as scheduling, vehicle routing, and personnel planning of­ ten only maintain bound consistency in constraints in­ volving time or other variables with large domains. As a consequence, complex rules on breaks, rest-times, and days-off provide only a poor propagation, which could be improved by arc consistency.

These examples illustrate that domain reduction does not de­ velop its full power in many real-world applications of con­ straint programming. Pruning power and, indirectly, solution quality are traded against short response times. In certain cir­ cumstances, such a trade-off can be avoided if the system fo­ cuses on the right deductions and computations. In this paper, Ulrich Junker ILOG S.A.

· A. Fabre's work has been carried out during a stay at ILOG.

1681, route des Do lines F-06560 Valbonne

ujunker®ilog.fr

we argue that preferences are one possible way for achiev­ ing this. As stated by Jon Doyle [Doyle, 2002], preferences can play different roles and need not only represent desider­ ata or user preferences. Preferences can also control reason­ ing meaning that only preferred inferences and domain reduc­ tions are made. Non-interesting deductions are left apart, but may become preferred if additional information is added.

We can easily apply this idea to typical backtrack tree search algorithms that maintain arc consistency when solv­ ing a constraint satisfaction problem. The crucial question is whether such an algorithm needs to achieve full arc consis­ tency and to remove all values that are not in the maximal arc-consistent domains. In [Schiex et al., 1996], it has been shown that the fails of the algorithm can be preserved if it simply constructs some arc-consistent domains, thus reduc­ ing the computation effort in average. In this paper, we show that the search algorithm can preserve its search strategy and the overall pruning if 1. the search algorithm uses a vari­ able and value ordering heuristics that can be described by (static) preference ordering between variables and values and 2. we construct some arc-consistent domains that contain the preferred values. The first condition is, for example, met by configuration problems [Junker and Mailharro, 2003] . The second condition needs some careful adaption of the defini­ tion of arc consistency, which will be elaborated in this paper.

We can thus cut down the propagation effort in each search node without changing the search tree, which leads to an over­ all gain if the search tree will not be explored completely. This happens if we are interested in one solution, the best so­ lution in a given time frame, or preferred solutions as defined in [Junker, 2002]. Arc consistency thus becomes more scal­ able and less dependent on the size of domains, which opens exciting perspectives for large-scale constraint programming.

We first introduce preferences (Section 2), use them to de­ fine a directed constraint graph (Section 3), and discuss arc consistency for preferred values (Sections 4 and 5). After introducing preferred supports (Section 6), we present the al­ gorithm Pref-AC (Section 7).

2 Preferred Solutions

In this paper, we consider constraint satisfaction problems of the following form. Let X be a set of variables and V be a set of values. A constraint c of arity kc has a sequence of vari­ ables X(c) = {x1 (c), ... , xkJc)} from X and a relation Rc that is a set of tuples from Vkc . Let C be a set of constraints. The triple (X, V, C) is then called a constraint network.

A solution of a constraint network is a mapping v of the variables X to the values in V such that each constraint is sat­ isfied, i.e., (v(x1(c)), ... , v(xkJc))) E Rc for all constraints c. The constraint satisfaction problem ( CSP) involves finding a solution of a constraint network.

Alternatively, we can represent the tuples by sets of assign­ ments of the form x = v between a variable x and a value v: if t is a tuple of the form ( v1 , ... , Vkc ) in Rc then let i be the set of assignments {x1 = v1 , . . . , Xkc = vkJ· Furthermore, let Rc be the set of all i such that t is in Rc. This represen­ tation will facilitate definitions and permits a straightforward logical characterization of a constraint c:

We further suppose that the following kinds of preferences are given. For each variable x, we introduce a strict partial or­ der --<x~ V x V among the possible values for x. This order can represent user preferences as occurring in configuration problems (cf. Dunker and Mailharro, 2003]). For example, the user might prefer a red car to a white car. Projecting pref­ erences on criteria to decision variables [Junker, 2002] also produces such an order (e.g. if price is minimized then try cheaper choices first) . Furthermore, we consider a strict par­ tial order --<x~ X x X between variables. For example, we may state that choosing a color is more important than choos­ ing a seat material and should therefore be done first. In the sequel, we suppose that the search procedure follows these preferences as described in [Junker and Mailharro, 2003] and always chooses a --<x-best variable and a --<x-best value for x. These preferences are given statically and thus correspond to a static variable and value ordering heuristics, which are usually sufficient for configuration problems.

We now use the preferences to define a preferred solu­ tion. First of all we choose a linearization of the orders --<x and --<x in form of total orders <x and <x that are super­ sets of the strict partial orders. Then we consider a ranking x(1) , ... x(n) of the variables in X that corresponds to the order <x, i.e., x(i) <x x(j) iff i < j. We then consider two solutions v1 and v2 and compare them lexicographically

Definition 1 A solution v of a constraint network P ·­ (X, V, C) is a preferred solution ofP iff there exist lineariza­ tions <x of --<x and <x of --<x for each x E X s.t. v is the best solution ofP w.r.t. the lexicographical order defined by <x and <x·

These preferred solutions correspond to the extreme solu­ tions in Dunker, 2002] that are obtained if all variables are criteria. If the search procedure follows the preferences then its first solution is a preferred solution. Hence, the notion of a preferred solution helps us to forecast the first solution in certain cases.

3 Preference-based Constraint Graph

In order to find a preferred solution, the search procedure chooses values for more important variables first. We will see later that, in some cases, we can anticipate a preferred so­ lution and construct it by a constraint propagation procedure if this procedure does not only follow the constraints, but also the order among the variables used by the search procedure.

In order to illustrate this, consider the bipartite constraint graph that connects the constraints with their variables. Sup­ pose that a variable x is connected via a constraint c to a less important variable y. Search will then assign a value to x and cause a domain reduction of y . We can thus say that the preferences --<x among variables impose an order on the con­ straint graph. For example, we will say that the arc between x and c leads from x to c and the arc between y and c leads from c toy.

We generalize this idea for arbitrary constraints and par­ tial orders. For each constraint c, we consider the --<x-best variables in X(c) and call them input variables. The other variables are called output variables. Arcs lead from input variables to a constraint and from there to the output vari­ ables.

Definition 2 Let (X, V, C) be a constraint network and --<x be a strict partial order between the variables X. A variable x of a constraint c is called input variable of c iff there is no other variable y of c s.t. y --<x x . A variable x of c is called output variable of c iff it is not an input variable of c. The directed constraint graph of the CSP is a bipartite graph having the nodes XU C and the set of arcs (x, c) s.t. x is an input variable of c and ( c, y) s. t. y is an output variable of c.

Each constraint can have several input and several output variables (cf. figure 1). If its variables are not comparable at all, then the constraint has no output variable, and it is a sink of the directed graph. However, each constraint has at least one input variable. As a consequence, no constraint can be a source of the directed graph. In general, the graph is not guar­ anteed to be acyclic, but it satisfies the following properties which are needed for our proofs: 1. All --<x-best variables of the set X are sources of the constraint graph since they cannot be an output variable of any constraint. However there can be sources that are not --<x-best variables. 2. If x is a ranking of the variables X that is a linearization of --<x then each output variable of each constraint is preceded by at least one input variable of the same constraint in the ranking.

4 Arc Consistency

A typical systematic search procedure for solving CSPs pro­ ceeds as follows. In each search node, it picks an assignment x = v for such a variable and creates two successor nodes, one for x = v and one for x =J v. Throughout the paper, we assume that a variable x is eliminated from the CSP of a successor node by a preprocessing step iff it has only a single possible value. Usually, the search procedure will not select an arbitrary assignment from the set A of all assignments, but tries to anticipate certain cases where the sub-tree of an assignment does not contain a solution. If such an assign­ ment is detected it is eliminated from A. Hence, the search procedure maintains a set A ~ A of possible assignments and considers only elements of A. Each solution can be charac­ terized by a subset of A that assigns exactly one value to each variable and that satisfies all constraints. As a consequence, if a variable x has no assignment in A then no solution exists and the search will backtrack. In the sequel, we write Ax for the set { v E V I (x = v) E A} of possible values for x in A.

Assignments can be eliminated from A if they lack a sup­ port on a constraint:

Definition 3 A set of assignments S is a support for x = v in c iff 1. SU {x = v} is an element of Rc and 2. (x = v) 'f. S.

Let s~=v be the set of supports for X = v in c. In this pa­ per, we are interested in search procedures that maintain arc consistency, i.e. that work with a set A where all assignments have supports S that are subsets of A and this on all relevant constraints:

Definition 4 Let A be a set of assignments. A subset A of A is an arc-consistent set of A iff 1. Ax is non empty for any x E X and 2. for all (x = v) E A and all constraints c of x, there exists a supportS for (x = v) inc such that Sis a subset of A.

If an arc-consistent set A contains a single assignment for each variable then A corresponds to a single solution. If no arc-consistent set exists then the CSP has no solution. Other­ wise, there is a unique maximal arc-consistent set, which is a superset of all arc-consistent sets, including the solutions.

Alternatively, we can consider a set~ of some assignments for which we know that they do not belong to any solution:

This can easily be translated to a reflexive and monotonic op­ erator that eliminates additional assignments:

Fixed-point theory then tells us that the transitive closure of this operator is the unique minimal set~* satisfying equation 3. As a consequence, the set A* of all assignments that are not eliminated (i.e., A* := A-~*) is the unique maximal set satisfying item 2 of def. 4. If each variable has an assignment in A* then A* is the maximal arc-consistent assignment. If some variable has no assignment in A* no arc-consistent as­ signment exists. In this case, no solution exists.

5 Arc Consistency for Preferred Values

Maintaining arc consistency prunes the search tree as follows:

• P1 if the current CSP is not arc-consistent then a fail occurs.
• P2 if a value v is not arc-consistent for a variable x then the search procedure will not assign v to x inside the current subtree.

In general , it is desirable to eliminate as many values as pos­ sible and to determine A* by applying an algorithm of the AC-family. The worst-case complexity is O(ICI · IVI 2 ) for binary constraints. If domains contain thousands or more el­ ements as is the case for typical scheduling problems and for configuration problems with large catalogs, then maintaining arc consistency is no longer feasible in practice.

Interestingly, it is not necessary to eliminate all assign­ ments of A - A*. [Schiex et al., 1996] try to construct a small arc-consistent set A. If this succeeds then pruning rule P1 cannot be triggered. This can lead to saving time in search nodes that are arc-consistent. We now want to extend this policy to pruning rule P2 in the case that the original search procedure uses the given preferences between variables and values in order to select an assignment. In each search state, the search procedure will pick a -<x-best variable and try out its possible values starting with the best value v*. If x = v* is not in the maximal arc-consistent set A* then we must en­ sure that it will be eliminated when constructing the subset A. However, if x = v* is in A* then we must ensure that it will be in the subset A.

Instead of doing a pure elimination process, we interleave construction and elimination steps and determine a set F of activated assignments, called focus, and a set~ of eliminated assignments. Both sets will grow during the process and our purpose is to obtain F - ~ as arc-consistent set. This set is sufficient for our search procedure if some properties are satisfied: 1. If x is a -<x-best variable and v is a -<x-best among the non-eliminated values of x then the search proce­ dure might pick x = v as next assignment. Hence, we have to activate it. 2. If an activated assignment does not have a sup­ port on a constraint c then it has to be eliminated. 3. The sup­ ports for the activated, but non-eliminated assignments must only contain activated and non-eliminated elements. 4. We need to guarantee that F - ~ contains at least one value per variable if an arc-consistent set exists. Since all variables can be reached from the sources via constraints, we activate best values for all sources of the directed constraint graph.

Definition 5 Let A be a set of initial assignments and F,!:::. be subsets of A s.t. !:::. s;; F. We say that (F, !:::.) is an -<­ activation of A iff the following properties hold:

1. If xis a source and (x = w) E I:::. for all w E A with w -<x v then x = v is in F.
2. 1f (x = v) E F, x E X(c), and c has no supportS for x = v s. t. S s;; A - !:::. then ( x = v) E !:::..

An -<-activation ( F, !:::. ) is stable iff all ( x = v) E F-!:::. have a supportS s;; F - /:::,. on all constraints c containing x.

Proposition 1 Let A be a set of initial assignments and !:::. * := PA (0). Then (A,!:::.*) is a stable activation.

Hence stable activations always exist and coincide with the maximal arc-consistent set in the worst case. Maintaining stable activations is sufficient to achieve pruning rules Pl and P2 for search procedures that always pick the best elements of A- !:::. (cf. figure 2):

Proposition 2 Let (F, !:::.) be a stable -<-activation of A. If there is no arc-consistent subset of A then there exists a vari­ able x s.t. F - !:::. does not contain an assignment for x. 1f there is an arc-consistent subset of A and A* is the maximal arc-consistent subset of A then the following properties hold:

1. F - !:::. is an arc-consistent subset of A.
2. If x is a -<x-best variable and x = v is a -<x-best as­ signment for x in A* then x = v is in F - !:::..
3. If x is a -<x-best variable, x = v is a -<x-best assign­ ment for x in A*, and w -<x v then x = w is in!:::..

If the search procedure chooses a -<-best assignment for a best variable in each step, then it will explore the same search tree independently of whether it maintains full arc consis­ tency or whether it maintains stable activations. Since the first solution found by the standard search procedure is a pre­ ferred solution, we will still obtain a preferred solution first if we maintain stable activations.

We now discuss how to actually construct stable -<­ activations. Initially, we activate the best assignments in A for all relevant variables by a monotonic operator ¢:

If an activated assignment is not supported by a constraint it will be eliminated and replaced by the next best assignments until we reach a set of assignments that have a support in each constraint. Unsupported assignments are eliminated by an operator b, which restricts p to the focus F:

We can iterate both operators if we combine them into an op­ erator a that maps a pair of assignment sets to a pair of assign­ ment sets s.t. aA((F, !:::.)) := (F U ¢A(6. ),!:::. U bA(F, !:::.)) . We easily obtain a lattice on these pairs if we define union and intersection of two pairs by applying these operations to both elements. The operator a A is monotonic and reflexive in this lattice and its transitive closure a :A ( ( F, !:::. ) ) is the smallest -<-activation (F* , !:::. *) that extends (F, !:::.) .

Next we discuss how an activation containing unsupported assignments can be extended to a stable one. We say that as­ signment x = v is unsupported on c in (F, !:::.) if c does not have a support S for x = v s.t. S s;; F - !:::. . If no such assignment exists, we have found a stable activation. Other­ wise, we pick an unsupported assignment, choose a support S for it, and activate the elements of this support. After this, we apply operator a A to produce a new activation:

Proposition 3 Let (F, !:::.) be an -<-activation/or A. Suppose x =vis unsupported on c in (F, !:::.) . Then c has a supportS forx = v s.t. S s;; A-1:::. and S g; F-1:::. and a:A((FUS, !:::.)) is an activation that supports x = v on c.

We can thus construct a stable activation as follows:

Definition 6 Let A be a set of initial assignments. Let 51 , ... , Sm be subsets of A. We then define (Fa, l:::.o) := a:A((0,0)) and (Fi,!:::.i) := a:A((Fi-1 U S;,f:::.;_l))fori = 1, .. . , m. The sequence 5 1 , ... , Sm is called an activation sequence iff I. S; g; F;- 1, 2. each Si is a support on a con­ straint cfor an assignment (x = v) in F;_1 - 1:::.; -1, and 3. (Fm, l:::.m) is stable.

Since F; has more elements than F;_1 and (A,p:A(0)) is a stable activation, we can show the following result, which permits the construction of stable activations:

Proposition 4 Let A be a set of initial assignments. There exists an activation sequence 51 , ... , Smfor A.

Figure 3 gives an idea of the possible gains. Once the dashed assignments have been eliminated, we activate only two assignments per variable, i.e. six in total, whereas an AC-algorithm would activate each of the 3 · lVI assignments in A. Hence, we obtain significant gains if domains are large and no elimination is required. The elimination of an assign­ ment still costs O(IVI) checks.

6 Preferred Supports

Preferences between values and variables allow us to define preferred supports. A support S s;; A - !:::. for an assignment x = v in constraint c can be considered a solution of the CSP (X(c),V,{c,x = v} U {y =/= w I (y = w) E !:::.}) . We say that S is a preferred support for x = v on c iff S is a preferred solution of this CSP. An assignment can have sev­ eral preferred supports. In case of binary constraint networks, preferred supports are unique if all domain orders -<x are to­ tal. In general, preferred supports are unique if additionally the order -<x is total as well.

Given a preferred solution, we cannot guarantee that each assignment has a preferred support in all constraints. How­ ever, if certain assignments in a solution S have preferred supports then S is preferred solution:

Proposition 5 Let S be a solution of P. Suppose that -<x and all -<x are strict total orders. If each assignment x = v to a source x of the direct constraint graph is a best assign­ ment for x in the unique maximal arc-consistent set A* and all activated assignments to input variables of a constraint c have a preferred support on c in S then S is a preferred solution ofP.

When constructing a stable activation, we choose preferred supports since this may result in a preferred solution:

Proposition 6 Suppose that -<x and all -<x are strict total orders. Let S1 , ... , Sm be an activation sequence and let (h b.i) be defined as in def 6. If I . each Si is a preferred support for some x =von some constraint c s.t. xis an input variable of cor x = vis unsupported on c in (Fi-1, b.i-d and 2. Fm - b.m is a solution of P then Fm - b.m is a preferred solution ofP.

The first condition in proposition 6 can be satisfied by al­ ways activating preferred supports. The second condition can be met by CSPs of a special structure. For example, consider a binary constraint network such that its directed constraint graph forms a tree (cf. figure 4). In this case, we only acti­ vate supports for assignments to input variables, but not for assignments to output variables, since each variable can only be an output variable of a single constraint. This result is, for example, interesting for certain car configuration prob­ lems and permits us to efficiently take into account certain user preferences.

Preferred solutions are also obtained in trivial cases:

Proposition 7 Suppose that -<x and all -<x are strict total orders. If there is a preferred solution containing all best values of all variables in A then it is equal to all activations produced /;Jy preferred supports.

7 Algorithm Pref-AC

In this Section, we present Pref-AC, an algorithm for comput­ ing an arc-consistent set A from a binary constraint network (X, D, C) . This algorithm activates supports for unsupported elements and meets the requirements of definitions 5 and 6, and proposition 6. An algorithm for non-binary constraints can be derived from this one. Pref-AC follows the princi­ ples of lazy arc consistency [Schiex et al., 1996] in order to build an arc-consistent set of assignments that is not neces­ sarily maximal. We base Pref-AC on AC-6 [Bessiere, 1994] for keeping the discussion simple, although we could exploit the hi-directionality of supports [Bessiere et at., 1999].

AC-6 assigns an ordering of the values in the domain of every variable Xi, checks one support (the first one or small­ est one with respect to the ordering) for each assignment (xi = a) on each constraint c(xi, Xj) to prove that (xi = a) is currently viable. When (x 1 = b) is found as the small­ est support of (xi =a) on c(xi,Xj ), (xi =a) is added to C S ( x 1 , b), the list of assignments currently having ( x j = b) as smallest support. If b is removed from the domain of Xj then AC-6 looks for the next support in the domain of Xj for each assignment Xi= a in CS(xj, b).

Pref-AC uses the domain order <x., a chosen linearization of -<x,, when looking for supports in the domain of a variable Xi . Furthermore, Pref-AC seeks supports only for elements of A, the current set of activated and non-eliminated values (i.e., F - b.). Pref-AC uses following data structure:

• Each variable Xi has a fixed initial domain Dx,, ordered by <x,, containing all values from D except those that violate unary constraints on Xi. The set b.( xi) := Dx - b.( xi) contains the values ofDx, that have not yet been removed by arc consistency.
• A is the arc-consistent set built by the algorithm.
• For each (xi = a) E A, a set CS(xi, a) contains the assignments that are currently supported by (xi =a) .
• The set Pending contains all the 4-tup1es (xi , a, Xj, b) such that a support for (Xi = a) has to be sought on c(xi, x1 ). If b -=f. nil, this means that all values of Xj better than b have already been removed.

Pref-AC uses two subprocedures (Algorithm 1). Procedure Acti vate(xi, a) adds an assignment (xi = a) to A, the set of current activated values. It initializes its data structure CS, and puts in Pending all the information needed to look for supports for (xi = a) on the constraints involving Xi. Function BestSup(xi, a, x1, b, B) looks for the best support for (xi = a) in B which is less preferred than b (we know there is no support in B better than or equal to b). B is b.(x1) or Axi depending on the status of Xi (input variable or not).

Pref-AC works as follows. We start by initializing b.(xi) to Dx. for each Xi (line 1 of Algorithm 2). We activate the best value of the best variable (line 2). Then, 4-tuples (xi, a, x1, b) are taken from the Pending set (line 4), and if (xi =a) is still active (line 5), we must seek a (new) support c for it. If Xi is an input variable of Cij, we seek the support in b. ( Xj) because we have to ensure that it will be a preferred support (lines 6 to 7). Otherwise, we first seek a support c among the activated, but non-eliminated elements (line 8). If none exists, we seek a new best support c (line 10) following def. 6. If c exists, we activate it if not yet done, and store the fact that it supports (xi = a) (lines 11 to 13). If no support exists for (xi = a), we remove it from b. and A (line 14). If b.(xi) is empty, a wipe out stops the procedure (line 15). If Xi is a source of the directed constraint graph and the best value of b.(xi) is not in Ax, ((xi =a) was the best of Ax, and b.( xi)), the best value

Algorithm 1: Subprocedures

procedure Activate (in x;: variable; a: value) Ax:; f-Ax; U {a}; CS(x;, a) f- 0; Pending f- {(x; ,a,xj, nil) I c(x;,xi) E C}; function BestSup (in x;; a; Xj; b; B): value I* returns the best value in B supporting (x; = a), or nil if not found*/; if b =nil then b f- best<x (B); 1 else if b > max(B) then return nil; b f- next<x . (b, B) ; 1 while ( b =!= nil) do if(a,b) Ec(x;,xj)then returnb; else b f- next<x. (b, B); 1 return nil;

of ~(xi) has to be activated (lines 16 to 18). Finally, we have to put in Pending the information needed to propagate the deletion of (Xi = a) (line 19).

Algorithm 2: Pref -AC

procedure Pref-AC() 1 ~(x;) f- Dx;, Vx; E X; Pending f- 0; 2 for each source x do Acti vate(x, best<x (~(x))); 3 while Pending =I= 0 do 4 pick (x;,a,xj,b) from Pending; 5 if(x; =a) E A then 6 if x; is an input variable of C;j then 7 Cf-BestSup(x;,a,xj,b,~(xi)); else 8 c f- BestSup(x;,a,Xj,b,AxJ); 9 if c = nil then 10 c f- BestSup(x;, a, Xj, b, ~(xi) - AxJ ); 11 if c =!= nil then 12 ifc rt AxJ thenActivate(xj,c); 13 put (x; = a) in CS(xi , c); else 14 ~(x;) f- ~(x;)- {a}; A f-A- {(x; =a)}; 15 if ~(x;) = 0 then return false; 16 if x; is a source then 17 ifbest<x; (~(x;)) rt Ax; then 18 Activate(best<x; (~(x;))); 19 for each (xj , b) E CS(x;, a) do put (xj, b, x;, a) in Pending; return true ;

If Pref-AC terminates with an empty set of pending prop­ agations (line 3), A only contains assignments for which a support has been activated on each constraint (because of line 12), and not deleted (because of line 19). In addition, this sup­ port is the preferred support for this assignment on this con­ straint if the variable was an input variable for the constraint (because of line 7 and the way Best Sup works). We know A contains at least an assignment per variable because of the activation of supports. Therefore, A is an arc-consistent set. And because of lines 16-18, we know that for each xi which is a source of X, the <x; -best of A;; is in Ax;.

The space complexity of Pref-AC is the same as AC-6, namely O([C[ · [V[), since in the worst case, all the values are activated and have a support stored on each constraint. The time complexity is also bounded above by that of AC-6, namely O([C[·[V[ 2 ), since for each value in each domain, we perform at most [V[ constraint checks on each constraint.

8 Conclusion

We have shown that it is sufficient to maintain an arc­ consistent set for the preferred choices of a search procedure. This can significantly speed up constraint solving if the vari­ able and value ordering heuristics of the search procedure can be described by preferences as is the case for typical configu­ ration problems. We developed an algorithm called Pref-AC for achieving this reduction and are currently testing it for configuration problems with large domains.

Many real-world applications of constraint programming suffer from insufficient propagation, since most approaches support only bound consistency for crucial constraints such as precedences of activities, resources, and rest-time rules. Adapting algorithm Pref-AC to those constraints provides an interesting future perspective for improving constraint solv­ ing in areas such as scheduling, personnel planning, and other logistics applications. Future work will be devoted to im­ prove Pref-AC such that it directly finds a preferred solution if the problem structure permits this (e.g. by activating pre­ ferred supports that are common to several variables).

Acknowledgements

We would like to thank Jean-Charles Regin and Olivier Lhomme for very helpful discussions.