Constraint programming techniques are widely used to model and solve interactive decision problems, an especially con guration problems. In this type of application, the con gurable product is described by means of a set of constraint bearing on the con guration variables. The user then interactively solves the CSP by assigning (and possibly, relaxing) the con guration variables according to her preferences. The aim of the system is then to keep the domains of the other variables consistent with these choices. Since maintaining of the global inverse consistency is generally not tractable, the domains are instead ltered according to some level of local consistency, e.g. arc-consistency. In the present work, we aim at o ering a more convenient interaction by providing the user with possible alternative values for each of the already assigned variables - i.e. the values that could replace the current one without leading to the violation of some constraint. We thus present the new concept of alternative domains in a (possibly) partially assigned CSP. We propose a propagation algorithm that computes all the alternative domains in a single step. Its worst case complexity is comparable with the one of the naive algorithm that would run a full propagation for each variable, but its experimental e ciency is much better.
The Constraint Satisfaction Problem (CSP) formalism o ers a powerful framework for representing a great variety of problems, e.g. routing problems, resource allocation, frequency assignment, con guration problems, etc. The main task addressed by the algorithms is the determination of the consistency of the CSP and/or the search for an (optimal) solution, and this is a di cult task: determining whether a CSP is consistent is an NP-complete request. In the CSP community, the main research stream thus addresses this question, either directly (looking for e cient complete algorithms) or getting around (studying the polynomial subclasses or proposing incomplete algorithms).
But these algorithms do not help solving decision support
problems that are interactive in essence. For such problems,
the user herself is in charge of the choice of values for the
variables and the role of the system is not to solve a CSP,
but to help the user in this task. Constraint-based product
con guration [
III,
France, email: components, options, or more generally by a set of attributes, the values of which have to be chosen by the user. These values must satisfy a nite set of con guration constraints that encode the feasibility of the product, the compatibility between components, their availability, etc.
Several extensions of the CSP paradigm have been
proposed in order to handle the constraints-based de nition of a
catalog or a range of products, and more speci cally the
definition of con gurable products. These extensions have been
motivated by di culties and characteristics that are speci c
to the modeling and the handling of catalogs of con gurable
products. Dynamic CSPs [
faction [
In this article, we do not deal with such representation problems: we assume that the product range is speci ed by a classical CSP. Instead, our work focuses on the human-computer interaction. When con guring a product, the user speci es her requirements by interactively giving values to variables. Each time a new choice is made, the domains of the variables must be pruned so as to ensure that the values available for the further variables can lead to a feasible product (i.e., a product satisfying all the initial con guration constraints): the aim of the system is to keep the domains of the other variables consistent with these choices. Since the maintaining of the global inverse consistency is generally not tractable, the domains are rather ltered according to some level of local consistency, e.g. arc-consistency. In the present paper, we propose to make this interaction more user-friendly by showing not only (locally) consistent domains, but also what we call the alternative domains of the assigned variables, i.e. the values that could replace the one of the assigned variable without leading to the violation of some constraint.
lematics of alternative domains is described in the next Section. Section 3 then develop the basis of our algorithm. Our rst experimental results are shown in Section 4. Proofs are gathered in Appendix. 2
A CSP is classically de ned by a triplet (X ; D; C) where X = fx1; : : : ; xmg is a nite set of m variables, each xi taking its values in a nite domain D(xi), and a nite set of constraints C. We note D = Qjn=1 D(xj ). An assignment t of a set of variable Y X is an element of the cartesian product of the domains of these variables; for any xj 2 Y we denote by t[xj ] the value assigned to xj in t.
viewed as a function from the set of assignments of vars(C) to f>; ?g: C(t) = > i t satis es the constraint; for any xj in vars(C) and any v in its domain, we say that an assignment t of vars(C) is a support of this value (more precisely, of (xj ; v) on C) i t[xj ] = v and t satis es C.
all the constraints. If such a solution exists, the CSP is said to be consistent, otherwise it is inconsistent.
(X ; D; C) and the current choices of the user by a set of couples
(xi; v) where xi is a variable in X and v the value assigned to
this variable. Following [
De nition 1 (A-CSP) An A-CSP is a 4-uple (X ; D; C; H) where (X ; D; C) is a CSP and H a nite set of constraints on variables of X .
choices, i.e. assignments of the variables: we suppose in the sequel of the paper that all the restrictions in H bear with different variables and restrict their domain to a unique value2; we will denote by hi = (xi v) the restriction from H on xi, if it exists.
After each choice, the system lters the variables' domains, ideally leaving only the values compatible with current choices. Since such a computation is intractable in the general case, a weaker level of consistency is ensured in real applications, generally arc-consistency. Recall that a CSP is said to be arc consistent in the general sense (GAC) i , for any variable xj 2 X and any value v in its domain, for any constraint C bearing on xj , there exists an assignment t of the variables of C in their domains such that t is a support of (xj ; v). The role of an arc consistency algorithm is to remove from the domains the values that do not have any support so as to compute a CSP that is equivalent to the original one (i.e. having the same set of solution) and that is arc consistent; this problem is called the closure by arc consistency of the original one.
Other, more powerful, levels of local consistency can be
ensured, e.g. Path Inverse Consistency [
De nition 2 (Current domain of a variable) Let l be a level of local consistency and P = (X ; D; C; H) an A-CSP. The current domain according to l of a variable xi is its 2 Actually, the de nitions and results could be set in a more general framework and capture any type of restriction; the meaning of alternative value when the restrictions in H are not unary is nevertheless questionable, hence our assumption. domain in the closure by l-consistency of (X ; D; C [ H) .
De nition 3 (Alternative domain) Let l be a level of local consistency and P = (X ; D; C; H) an A-CSP. The alternative domain of a variable xi according to l is its domain in the closure by l-consistency of the l CSP(X ; D; C [ H n fhig). We write it Dalt(xi).
A value v is thus an alternative value for xi either if it belongs to the current domain of xi (it is in particular the case when xi is assigned to v), or if (i) xi is assigned another value than v and (ii) the single relaxation of this assignment would make v l-consistent. For instance, if xi is the last assigned variable, all the values that were in the domain of xi just before its assignment are alternative values.
Example 1 Consider the CSP X = fx1; x2; x3g; D = D1 D2 D3 = f1; 2; 3; 4g3; C = fAlldif f (x1; x2; x3)g ; initially, H = ; and the current domains of the three variables are DC (x1) = DC (x2) = DC (x3) = f1; 2; 3; 4g. In this example, we suppose that that arc consistency is maintained. Let theuser rst assign value 1 to x1. We get H = f(x1 = 1)g ; then DC (x1) = f1g and arc consistency removes value 1 from the current domains of x2 and x3: DC (x2) = DC (x3) = f2; 3; 4g. At this step, x1 is the only assigned variable and has three alternative values, 2, 3 and 4.
Suppose that the user then assigns value 4 to x2, i.e. H = f(x1 = 1); (x2 = 4)g ; arc consistency, removes 4 from the current domains of x2 and x3: DC (x2) = DC (x3) = f2; 3g while DC (x1) = f1g and DC (x2) = f4g . x1 has only two alternative values left : 2 and 3; 4 is not alternative anymore since it does not belong to the closure by arc consistency of the CSP < X = fx1; x2; x3g; D = D1 D2 D3 = f1; 2; 3; 4g3; C = fAlldif f (x1; x2; x3)[fx2 = 4gg >. x2 has also two alternative values, 2 and 3 (see Table 1).
x1 x2 x3 1 ? 2 3 4 ?
The notion of alternative domain is orthogonal to the
notion of removal's explanation, such as proposed in PaLM [
The notion of alternative domain can be compared to the
concept of fault tolerant solution [
When n variables are assigned, a naive way of computing the alternative domains of these variables is to make n + 1 copies of the CSP: a reference CSP P0 (where all the n variables are assigned), and n CSP Pi where each Pi has exactly the same assignments than P0, with the exception of the assignment of variable xi. Each Pi is ltered by l-consistency. The alternative domain of variable xi is obviously the domain of xi in the arc consistent closure of Pi. This method does not require much space but does a lot of redundant computations.
3.1
removed by the ltering algorithm, a vector of boolean ags, one ag for each hi 2 H. The ag on hi must be true if and only if the single relaxation of the user's choice hi will lead to have the value back in the domain of its variable. Let us formalize: De nition 4 (Removal, invalid tuple) Let P = (X ; D; C; H) be an A-CSP and P l the closure of (X ; D; C [ H) by some level of local consistency l. A removal w.r.t. a level l of local consistency is a pair (xj ; v), xj 2 X ; v 2 D(xj ) such that v does not belong to the domain of xj in P l We write Rl the set of removals of P w.r.t. l.
Let C a constraint in C and t an assignment of vars(C) satisfying C. t is said to be invalid w.r.t. l i there exists xj 2 vars(C) such that t[xj ] does not belong to domain of xj in P l; otherwise, it is said to be valid w.r.t. l.
(xj 6= v), and we will omit to mention level l to which the removal refers when not ambiguous.
De nition 5 (Su cient Justi cation of a removal) Let P = (X ; Dlt;hCe; Hse)t obef Pa n0sAre-CmSoPva,l laaccolervdeilngoftololc.al consistency, and R
An user choice hi 2 H is said to be an l-su cient justi cation of a removal (xj 6= v) 2 Rl if and only if v belongs to the domain of xj in the l-consistent closure of (X ; D; C [Hnfhig).
By extension, for any xj in X and any v in D(xj ), hi 2 H is said to be an l-su cient justi cation of v for xj if and only if v belongs to the domain of xj in the l-consistent closure of (X ; D; C [ H n fhig).
to the removal of the value v in the domain of x, this assignment is a su cient justi cation of x 6= v. By extension, any hi is a su cient justi cation of a value that does belongs to the current domain of its variable.
and x2 are assigned, H contains two assumptions: h1 = (x1 = 1) , and h2 = (x2 = 4).
h1 (resp. h2) as a (sole) su cient justi cation.
of x2 and x3. h1 is a su cent justi cation for the removals (x2 6= 1) and (x3 6= 1), and h2 a su cient justi cation of (x2 6= 4) and (x3 6= 4).
mains of their variables receive both h1 and h2 as a su cient justi cations.
X = fx1; x2; x3; x4g; D = D1 D2 D3 D4 = f1; 2; 3g4; C = fx1 6= x2; x3 6= x2; x4 6= x2)g. Value 2 for x1 has two supports on x2 : 1 and 3. Suppose that the user has assigned value 1 to x3 (h3) and value 3 to x4 (h4); in other terms, H = f(x3 = 1); (x4 = 3)g. h3 forbidds the rst support of x1 = 2 and h4 forbids its second support ; value 2 is thus removed by arc consistency from the current domain of x1: DC (x1) = f1; 3g and this removal has two su cient justi cations: h3 and h4.
an assigned variable xi i hi is a su cient justi cation of the removal (xi 6= v): Proposition 6 Let P = (X ; D; C; H) be an A-CSP, l a level of local consistency.
For any xi 2 X , any v 2 D(xi), v belongs to the alternative domain of xi i either v belongs to the domain of xi in the closure by l consistency of P = (X ; D; C [H) or (xi 6= v) 2 Rl and hi is a su cient justi cation of (xi 6= v).
The notion of su cient justi cation is extended to tuples as follows: removals t1 ? ? t2 ? ? t3 ? fh1g fh2g fh2; h4g t4 ? ? ; De nition 7 (Su cient justi cation of a tuple) Let P = (X ; D; C; H) be an A-CSP, l a level of local consistency, C a constraint in C and t an assignment of vars(C) satisfying C.
An user choice hi 2 H is said to be an l- su cient justi cation for t if and only if, for each xj 2 vars(t), t[xj ] belongs to the domain of xj in the closure by l consistency of the CSP (X ; D; C [ H n fhig).
Example 1 (cont') If we go back to example 1, once x1 and x2 have been assigned, tupple (3; 2; 4) is not valid anymore and has one su cient justi cation, h1 (it is enough to relax x1 = 1 to make this tupple valid again); remark that tupple (4; 2; 1), that is also invalid, has no su cient justi cation (the relaxation of the two choices is necessary to make it valid again).
is an l-su cient justi cation for the tuple t if and only if, for each xj involved by the tuple, either t[xj ] is in the current domain of xj or hi is a su cient justi cation of the removal (xj 6= t[xj ]). Formally, let us call the con ict set of t the set of removals that make it invalid: De nition 8 (Con ict set) The con ict set of a tuple t w.r.t. some level of l consistency is the subset of Rl de ned by: CS(t) = f(xi 6= v) 2 Rl s. t. t[xi] = vg.
Proposition 9 hi is an l-su cient justi cation of a tuple t if and only it is an l-su cient justi cation of each of the removals in its con ict set w.r.t. l.
Proposition 10 hi is a su cient justi cation w.r.t. Arc consistency (GAC) for a removal (x 6= v) i , for each constraint C bearing on x, there exists a tuple t support of (x = v) on C such that hi is GAC-su cient justi cation of t.
Similar properties can be established for other levels of local
consistency based on the notion of support, typically for k
inverse consistency [
hi 2 H is a (1; k)-su cient justi cation of (x 6= v) 2 R(1;k) i , for each set V of k variables there exists a support t of x = v on V such as hi is a (1; k)-su cient justi cation of t. 3.2
alternative domains w.r.t. Arc
to be taken into account are mostly table constraints and the level of consistency referred to is Generalized Arc Consistency.
the assignment of a variable using an extension of GAC4 [
Sxi;v;C is the set of supports of (xi; v) on C and
for any tuple t, ft is its vector of justi cations; for any removal (xi 6= v) f(xi6=v) is its vector of justi cations; for any removal (xi 6= v) and any constraint C bearing on xi, f(xi6=v;C) is the vector of justi cation of (xi 6= v) on C.
The di erence with GAC4 is that a removal (x 6= v) must be propagated non only when it is created, but for each change in its vector of justi cations. Since the updating of the vectors of justi cation is monotonic (a hi might go from being sufcient to not, but not the other way around), the algorithm terminates. More precisely, instead of entering just once in Q, each removal can enter in the queue n times at most (n being the number of hi in H), i.e.as much as the number of possible changes in a vector of justi cations. The worst case complexity is thus bounded by O(nedk) with e the number of constraints, m the number of variables, n the maximal number of assumptions (typically, n = m), d the maximum size of the domains and k the maximum arity of constraints. It is thus the same complexity as the GAC-4 based naive method: n:O(e:dk). With the important di erence that in the naive method, GAC-4 is called exactly n times while n is a worst case bound for justi cation-based algorithm.
port Si;v;C for each xi , each value v in its domain and each constraint C bearing on xi; Let say that this structure is in O(T ) ( T is actually proportional to the space taken by valid tuples in constraint tables). Our algorithm also maintains, for each tuple t, a vector of n ags, meaning a O(T:n) space. For each removal and each constraint bearing on the variable of the removal, we also keep a vector of n boolean ags. Since the number of removals is bounded by the number of variable/value pairs (xi; v) in the problem, the algorithm involves in the worst case as many boolean vectors as the number of
tion bounded by O(n:T ).
Procedure Initialize((X ; D; C):CSP; n: integer) /* (X ; D; C) is the original CSP assumed to be arc consistent */ /* All the tuples are supposed to be valid */ /* n is the maximal number of assumptions to be considered */ begin foreach C 2 C do foreach xi 2 vars(C), v 2 D(xi) do
Cpt(xi; v; C) := 0; end end
Si;v;C = ; end foreach t 2 T able(C) do ft = Truen; valid(t) = True; CS(t) = Falsen; foreach xi 2 vars(C) do
Cpt(xi; t[xi]; C) + +;
Add t to Si;t[xi];C end end
initial CSP; H: the past assumptions; Dc: the current domains); Add (xk; w) to H; Q := ;; /* The removal of the other values in the current domain of xk is due to hk */ foreach u 6= w 2 Dc(xk) do f(xk6=u) Falsem; f(xk6=u)[hk] True; end Add (xk 6= u) to Q; while Q 6= ; do
Choose and remove a (xi 6= v) from Q; if v 2 Dc(xi) then
end foreach C s.t. xi 2 vars(C) and each tuple t in Si;v;C do
M em ft; ft ft ^ f(xi6=v); if valid(t) then foreach xj 2 vars(t) s.t. j 6= i do
Cpt(xj; t[xj]; C) ; if Cpt(xj; t[xj]; C) == 0 then f(xj6=t[xj]);C Falsem /* init; will be computed later */ ; Add (xj 6= t[xj]) to Q; if t[xj] 2 Dc(xj) then
f(xj6=t[xj]) Truem /* init */ ; end end end valid(t) = f alse;
end end if M em! = ft /* A justif. of t is not su cient anymore */ then foreach xj 2 vars(t) s.t. j 6= i do mem0 = f(xj6=t[xj]); f(xj6=t[xj]);C = f(xj6=t[xj]);C _ ft; fxj6=t[xj] = fxj6=t[xj] ^ fxj6=t[xj];C ; if mem0 6= f(xj6=t[xj]) then
Add (xj 6= t[xj]) to Q; end end end
end end end foreach hi 2 H do
Dalt(xi) = ;; foreach v 2 Dxi do if f(xi 6= v)[hi] then
Add v to Dalt(xi) end Algorithm 2: Propagation of decision hk = (xk w)
lem of con guration. It involves 32 variables of domain of size 2 to 10, 35 binary constraints. The product to con gure is a blowing machine, which blows bottles for di erent matters. The benchark can be found at url ftp://ftp.irit.fr/pub/IRIT/ADRIA/PapersFargier/Config/souffleuse.xml.
The protocol simulates 1000 sessions of con gurations as follows. First, a sample of 1000 consistent complete assignments is randomly red. For each of then, the corresponding session is simulated by assigning the variables following a random (uniform) order. After each assignment, we measure the cpu time needed to make the current problem arc-consistent and to compute the alternative domains of all the already assigned variables are computed. The whole protocol is applied by both the justi cation-based algorithm described in the previous Section and the naive method (that works on as may copies of the original CSP as the number of user choices in H, as decribed in introduction of Section 3 ) ; for the shake of rigor, the two algorithms play on the same assignments and the same assignment orders.
Figure 1 presents the result of these experiments. On the x-axis is the number of the assignment in the sequence; the y-axis is logarithmic and indicates the mean cpu time need for the naive method (plain line, with rounds) and for the justi cation-based algorithm dotted line, with squares.
The results are quite good: our algorithm is faster as soon as more than 5 variables are assigned, i.e.when more than
time required by the naive algorithm grows linearly with the number of variables, while our algorithm has stable computation time. These rst results have obviously to be con rmed by more experiments on bigger con guration problems. 5
domain of a variable with respect to a local consistency level and proposed an extension of GAC4 algorithm as a way to compute the alternative domains when maintaining General
tion algorithm as many times as the number of alternative domains to be computed, our approach keeps limited justi cations of the removals. Tested on two industrial benchmarks, this method quickly outperforms the naive method.
The main limitation of our method is obviously its space consumption; the extra space consumption depends directly of the number of variables for which we want to compute the alternative domain. This being said, it should be kept in mind that for practical purposes the system is not asked to display all the alternative domains; the human user has with a limited mental capacity and it is not obvious that she can or even wants to see a lot of alternative domains at a glance. In a con guration application for instance, the user looks at only a small number of variable simultaneously, typically the ones involved in the subcomponent currently being con gured.
The concepts we have coined are close to the notion of value restoration. In the current work, we focused on the computation of alternative domains; an alternative value is a forbidden value that can be restored by the sole relaxation of the assignment of its variable. But more generally any value having at least one su cient justi cation can be restored by the relaxation of only one assignment. For each value in the domain of an assigned variable, the user knows whether she can change her choice to this value without modifying the other choices this is the notion alternative domain. But the user also knows something about the values that have been ltered from the domains of the unassigned variables: the justi cation vector of such a value provides her with the set of , previous choices (on other variables) she could relax in order to make the value available again. Hence the potential use of the algorithm proposed by this paper to provide the user with alternative values in a wider sense, and more generally to support the task of interactive relaxation by providing easily restorable values.
This work has a huge potential for developments and
perspectives. Firstly, our algorithm obviously needs to be
improved, for instance with a lazy implementation, and our
experiments must be completed. Secondly, we should think
about the extension of the maintenance of alternative domain
in CSP with general constraints, and not just in table
constraints ; such an algorithm is not too di cult to conceive for
CSPs involving binary constraints only, but the task seems
much more tricky for general constraints. Finally, we should
be able to consider the whole interaction; for the moment, we
only considered the assignment of a value to a variable: we
need to study the relaxation of choices also. This adaptation
might mean an hybridizing with the maintenance algorithms
of propagation/depropagation in dynamic CSP[
A
[Proof of Proposition 9] Of course, the proposition holds when t is valid (it has an empty con ict set). Let us examine the case of an invalid tuple.
) Let hi be l-su cient justi cation of an invalid tuple t and suppose that there exists a removal (x 6= v) in the con ict set of t such that hi is not a su cient justi cation of (x 6= v).
We write Pil the l-consistent closure of (X ; D; C [ H n fhig).
valid in Pil. Since hi is also not a su cient justi cation of (x 6= v), v is not in the domain of x in Pil; t is thus invalid in
( Reciprocally, let hi be an l-su cient justi cation of all the removals in the con ict set of t. For each of these (xj 6= vj ), vj is by de nition in the domain of xj in Pil. Thus, t is a valid tuple in Pil - by de nition of the notion of justi cation, hi is thus an l-su cient justi cation of t. 2 [Proof of Proposition 10] ) Let hi be a GAC su cient justi cation of a removal (x 6= v) . Suppose that there exits a constraint C bearing on x such that none of the supports of x = v on C admits hi as a su cient justi cation. This means that these tuples are not valid in the arc consistent closure of (X ; D; C [ H n fhig) (denoted PiGAC ). Thus v has no support on C in PiGAC : it does not belongs to the domain of x in PiGAC ; hi is thus not a su cient justi cation of (x 6= v) .
( Reciprocally, consider an assumption hi and suppose that 8C bearing x, 9t support of x = v such that hi is a GAC su cient justi cation of t . This means that, for any constraint bearing on x there exists a support t of x = v valid in PiGAC ; v thus belongs to the domain of x in PiGAC - by de nition, this meant that hi is a GAC-su cient justi cation of (x 6= v). 2 [Proof of Proposition 11] 8(x1; :::; xk); 9(v1; :::; vk) a support of x = v such that hi is a (1; k)-su cient justi cation of (v1; :::; vk)
, 8(x1; :::; xk); 9(v1; :::; vk) support of x = v such that any of the vj belongs to the domain of its variable in the closure by (1; k)-consistency of (X ; D; C [ H n fhig)
, v belongs to the domain of x the closure by (1; k)consistency of (X ; D; C [ H n fhig) (de nition of the 1; k consistency) , hi is a justi cation (1; k)-su cient of x 6= v. 2 [Proof of Proposition 12]
C;x2vars(C) t2Support(x;v;C) ft[hi] For any hi, any x 2 X and any v 2 Dx. I.e.: