=Paper=
{{Paper
|id=None
|storemode=property
|title=Maintaining Alternative Values in Constraint-based Configuration
|pdfUrl=https://ceur-ws.org/Vol-958/paper1.pdf
|volume=Vol-958
|dblpUrl=https://dblp.org/rec/conf/confws/BeckerF12
}}
==Maintaining Alternative Values in Constraint-based Configuration==
https://ceur-ws.org/Vol-958/paper1.pdf
Maintaining alternative values in
constraint-based configuration
Caroline Becker and Hélène Fargier 1
Abstract. Constraint programming techniques are widely components, options, or more generally by a set of attributes,
used to model and solve interactive decision problems, an es- the values of which have to be chosen by the user. These
pecially configuration problems. In this type of application, values must satisfy a finite set of configuration constraints
the configurable product is described by means of a set of con- that encode the feasibility of the product, the compatibility
straint bearing on the configuration variables. The user then between components, their availability, etc.
interactively solves the CSP by assigning (and possibly, relax- Several extensions of the CSP paradigm have been pro-
ing) the configuration variables according to her preferences. posed in order to handle the constraints-based definition of a
The aim of the system is then to keep the domains of the other catalog or a range of products, and more specifically the def-
variables consistent with these choices. Since maintaining of inition of configurable products. These extensions have been
the global inverse consistency is generally not tractable, the motivated by difficulties and characteristics that are specific
domains are instead filtered according to some level of local to the modeling and the handling of catalogs of configurable
consistency, e.g. arc-consistency. products. Dynamic CSPs [13], for instance suit the problems
In the present work, we aim at offering a more convenient where the existence of some optional variables depends on
interaction by providing the user with possible alternative val- the value of another variable. Other extensions proposed by
ues for each of the already assigned variables - i.e. the values the CSP community include composite CSPs [17], interactive
that could replace the current one without leading to the vio- CSPs [10], hypothesis CSPs [1], generative constraint satis-
lation of some constraint. We thus present the new concept of faction [19, 7], etc.
alternative domains in a (possibly) partially assigned CSP. In this article, we do not deal with such representation prob-
We propose a propagation algorithm that computes all the al- lems: we assume that the product range is specified by a clas-
ternative domains in a single step. Its worst case complexity sical CSP. Instead, our work focuses on the human-computer
is comparable with the one of the naive algorithm that would interaction. When configuring a product, the user specifies her
run a full propagation for each variable, but its experimental requirements by interactively giving values to variables. Each
efficiency is much better. time a new choice is made, the domains of the variables must
be pruned so as to ensure that the values available for the fur-
ther variables can lead to a feasible product (i.e., a product
1 Introduction satisfying all the initial configuration constraints): the aim of
The Constraint Satisfaction Problem (CSP) formalism offers the system is to keep the domains of the other variables con-
a powerful framework for representing a great variety of prob- sistent with these choices. Since the maintaining of the global
lems, e.g. routing problems, resource allocation, frequency inverse consistency is generally not tractable, the domains are
assignment, configuration problems, etc. The main task ad- rather filtered according to some level of local consistency, e.g.
dressed by the algorithms is the determination of the consis- arc-consistency. In the present paper, we propose to make this
tency of the CSP and/or the search for an (optimal) solution, interaction more user-friendly by showing not only (locally)
and this is a difficult task: determining whether a CSP is con- consistent domains, but also what we call the alternative do-
sistent is an NP-complete request. In the CSP community, mains of the assigned variables, i.e. the values that could re-
the main research stream thus addresses this question, either place the one of the assigned variable without leading to the
directly (looking for efficient complete algorithms) or getting violation of some constraint.
around (studying the polynomial subclasses or proposing in- The structure of the present article is as follows: the prob-
complete algorithms). lematics of alternative domains is described in the next Sec-
But these algorithms do not help solving decision support tion. Section 3 then develop the basis of our algorithm. Our
problems that are interactive in essence. For such problems, first experimental results are shown in Section 4. Proofs are
the user herself is in charge of the choice of values for the gathered in Appendix.
variables and the role of the system is not to solve a CSP,
but to help the user in this task. Constraint-based product
configuration [14, 18, 12, 19, 20] is a typical example of such 2 Background and Problematics
problems: a configurable product is defined by a finite set of
A CSP is classically defined by a triplet (X , D, C) where X =
1 IRIT, University Toulouse III, France, email: {x1 , . . . , xm } is a finite set of m variables, each xi taking its
{becker,fargier}@irit.fr values in a finite domain D(xi ), and a finite set of constraints
C. We note D = n
Q
j=1 D(xj ). An assignment t of a set of domain in the closure by l-consistency of (X , D, C ∪ H) .
variable Y ⊆ X is an element of the cartesian product of the
domains of these variables; for any xj ∈ Y we denote by t[xj ]
the value assigned to xj in t. We can now formally define the notion of alternative do-
A constraint C in C involves a set vars(C) ⊆ X and can be main of an assigned variable as the current domain that it
viewed as a function from the set of assignments of vars(C) would have if the user would take this assignment back:
to {>, ⊥}: C(t) = > iff t satisfies the constraint; for any xj in
vars(C) and any v in its domain, we say that an assignment t Definition 3 (Alternative domain)
of vars(C) is a support of this value (more precisely, of (xj , v) Let l be a level of local consistency and P = (X , D, C, H)
on C) iff t[xj ] = v and t satisfies C. an A-CSP. The alternative domain of a variable xi accord-
An assignment t of X is a solution of the CSP iff it satisfies ing to l is its domain in the closure by l-consistency of the
all the constraints. If such a solution exists, the CSP is said CSP(X , D, C ∪ H \ {hi }). We write it Dalt l
(xi ).
to be consistent, otherwise it is inconsistent.
Formally, a configurable product is represented as a CSP
A value v is thus an alternative value for xi either if it
(X , D, C) and the current choices of the user by a set of couples
belongs to the current domain of xi (it is in particular the case
(xi , v) where xi is a variable in X and v the value assigned to
when xi is assigned to v), or if (i) xi is assigned another value
this variable. Following [1], the problem can be represented
than v and (ii) the single relaxation of this assignment would
by an Assumption-based CSP (A-CSP).
make v l-consistent. For instance, if xi is the last assigned
variable, all the values that were in the domain of xi just
Definition 1 (A-CSP) An A-CSP is a 4-uple (X , D, C, H) before its assignment are alternative values.
where (X , D, C) is a CSP and H a finite set of constraints on
variables of X .
Example 1 Consider the CSP X = {x1 , x2 , x3 }, D = D1 ×
In configuration, H represents the set of current user D2 × D3 = {1, 2, 3, 4}3 , C = {Alldif f (x1 , x2 , x3 )} ; initially,
choices, i.e. assignments of the variables: we suppose in the H = ∅ and the current domains of the three variables are
sequel of the paper that all the restrictions in H bear with dif- DC (x1 ) = DC (x2 ) = DC (x3 ) = {1, 2, 3, 4}. In this example,
ferent variables and restrict their domain to a unique value2 ; we suppose that that arc consistency is maintained.
we will denote by hi = (xi ← v) the restriction from H on xi , Let theuser first assign value 1 to x1 . We get H = {(x1 = 1)}
if it exists. ; then DC (x1 ) = {1} and arc consistency removes value 1
After each choice, the system filters the variables’ do- from the current domains of x2 and x3 : DC (x2 ) = DC (x3 ) =
mains, ideally leaving only the values compatible with cur- {2, 3, 4}. At this step, x1 is the only assigned variable and has
rent choices. Since such a computation is intractable in the three alternative values, 2, 3 and 4.
general case, a weaker level of consistency is ensured in real Suppose that the user then assigns value 4 to x2 , i.e. H =
applications, generally arc-consistency. Recall that a CSP is {(x1 = 1), (x2 = 4)} ; arc consistency, removes 4 from the
said to be arc consistent in the general sense (GAC) iff, for current domains of x2 and x3 : DC (x2 ) = DC (x3 ) = {2, 3}
any variable xj ∈ X and any value v in its domain, for any while DC (x1 ) = {1} and DC (x2 ) = {4} . x1 has only two
constraint C bearing on xj , there exists an assignment t of alternative values left : 2 and 3; 4 is not alternative anymore
the variables of C in their domains such that t is a support of since it does not belong to the closure by arc consistency of the
(xj , v). The role of an arc consistency algorithm is to remove CSP < X = {x1 , x2 , x3 }, D = D1 ×D2 ×D3 = {1, 2, 3, 4}3 , C =
from the domains the values that do not have any support so {Alldif f (x1 , x2 , x3 )∪{x2 = 4}} >. x2 has also two alternative
as to compute a CSP that is equivalent to the original one values, 2 and 3 (see Table 1).
(i.e. having the same set of solution) and that is arc consis-
tent; this problem is called the closure by arc consistency of 1 2 3 4
the original one. x1 ? ×
x2 × ?
Other, more powerful, levels of local consistency can be en- x3 × ×
sured, e.g. Path Inverse Consistency [4], Singleton Arc Con-
sistency [5], k-inverse consistency [8, 9]. In the following defi-
nitions, we do not make any assumption on the level of local Table 1. Assigned (?), forbidden (×) and alternative () values
for the A-CSP X = {x1 , x2 , x3 }, D = D1 × D2 × D3 = {1, 2, 3, 4}3 ,
consistency that is ensured. We simply consider that, after C = {Alldif f (x1 , x2 , x3 )}, H = {(x1 ← 1), (x2 ← 4)}).
each choice, an algorithm is called that ensures some level l
of local consistency - i.e. that computes the closure by l con-
sistency of the original problem. We call the current domain
of a variable its domain in this closure. The notion of alternative domain is orthogonal to the no-
tion of removal’s explanation, such as proposed in PaLM [16]:
Definition 2 (Current domain of a variable) Let l be a explanations are a way to explain the pruning of the domains
level of local consistency and P = (X , D, C, H) an A-CSP. and aim at proposing a strategy of restoration of some value
The current domain according to l of a variable xi is its for an unassigned variable by the relaxation of a (minimal)
2 Actually, the definitions and results could be set in a more gen- subset of user’s choices. On the contrary, the alternative do-
eral framework and capture any type of restriction; the meaning main of a variable provides a way to change the value of an
of alternative value when the restrictions in H are not unary is assigned variable without any modification of the other user
nevertheless questionable, hence our assumption. choices.
The notion of alternative domain can be compared to the To improve readability, a removal (xj , v) will often be written
concept of fault tolerant solution [21]. A fault tolerant solu- (xj 6= v), and we will omit to mention level l to which the
tion is actually a solution such as all the variables have a removal refers when not ambiguous.
non-empty alternative domain: if one of the current value in
the assignment is made unavailable for any reason, a solution Definition 5 (Sufficient Justification of a removal)
can still be found by choosing a value from its alternative do- Let P = (X , D, C, H) be an A-CSP, l a level of local consis-
main - this value is by definition compatible with the other tency, and Rl the set of P 0 s removal according to l.
choices. The notion has been generalized by Hebrard et al. An user choice hi ∈ H is said to be an l-sufficient justifica-
[11] under the name ”super-solutions”. The main difference tion of a removal (xj 6= v) ∈ Rl if and only if v belongs to the
between the notion of fault tolerant solutions and the notion domain of xj in the l-consistent closure of (X , D, C ∪H\{hi }).
of alternative domains is that fault tolerant solutions deal
with complete assignments while alternative domains sug- By extension, for any xj in X and any v in D(xj ), hi ∈ H
gests restoration values for partial assignments also. It should is said to be an l-sufficient justification of v for xj if and only
also be noticed that the two notions target different practical if v belongs to the domain of xj in the l-consistent closure of
goals: when refereing to a super-solution, the one in looking (X , D, C ∪ H \ {hi }).
for some, but not all, robust (and complete ) solutions - there
is indeed a potentially exponential number of fault tolerant
solutions. When computing alternative domains, we are look- For instance, if the propagation of the last assignment leads
ing for all the alternative values, and this even during the to the removal of the value v in the domain of x, this assign-
search, when the assignments are partial. ment is a sufficient justification of x 6= v. By extension, any
hi is a sufficient justification of a value that does belongs to
the current domain of its variable.
3 Computing alternative domains
Example 1 (cont’) If we go back to example 1, once x1
When n variables are assigned, a naive way of computing the and x2 are assigned, H contains two assumptions: h1 = (x1 =
alternative domains of these variables is to make n + 1 copies 1) , and h2 = (x2 = 4).
of the CSP: a reference CSP P0 (where all the n variables All the values deleted from the domain of x1 (resp. x2 ), have
are assigned), and n CSP Pi where each Pi has exactly the h1 (resp. h2 ) as a (sole) sufficient justification.
same assignments than P0 , with the exception of the assign- Arc consistency has removed values 1 and 4 from the domains
ment of variable xi . Each Pi is filtered by l-consistency. The of x2 and x3 . h1 is a sufficent justification for the removals
alternative domain of variable xi is obviously the domain of (x2 6= 1) and (x3 6= 1), and h2 a sufficient justification of
xi in the arc consistent closure of Pi . This method does not (x2 6= 4) and (x3 6= 4).
require much space but does a lot of redundant computations. By convention, all the values that are still in the current do-
It will be the reference point from our method, which follows mains of their variables receive both h1 and h2 as a sufficient
the opposite philosophy: memorizing information in order to justifications.
avoid a duplicate work.
Example 2 A removal may have several sufficient justifica-
tions, as shown by the following example. Consider the CSP
3.1 Removals and sufficient justifications X = {x1 , x2 , x3 , x4 }, D = D1 × D2 × D3 × D4 = {1, 2, 3}4 ,
C = {x1 6= x2 , x3 6= x2 , x4 6= x2 )}. Value 2 for x1 has two
The main idea of our approach is to maintain, for each value supports on x2 : 1 and 3. Suppose that the user has assigned
removed by the filtering algorithm, a vector of boolean flags, value 1 to x3 (h3 ) and value 3 to x4 (h4 ); in other terms,
one flag for each hi ∈ H. The flag on hi must be true if and H = {(x3 = 1), (x4 = 3)}. h3 forbidds the first support
only if the single relaxation of the user’s choice hi will lead of x1 = 2 and h4 forbids its second support ; value 2 is
to have the value back in the domain of its variable. Let us thus removed by arc consistency from the current domain
formalize: of x1 : DC (x1 ) = {1, 3} and this removal has two sufficient
justifications: h3 and h4 .
Definition 4 (Removal, invalid tuple)
Let P = (X , D, C, H) be an A-CSP and P l the closure of Of course, a value belongs v to the alternative domain of
(X , D, C ∪ H) by some level of local consistency l. an assigned variable xi iff hi is a sufficient justification of the
removal (xi 6= v):
A removal w.r.t. a level l of local consistency is a pair (xj , v),
xj ∈ X , v ∈ D(xj ) such that v does not belong to the domain Proposition 6 Let P = (X , D, C, H) be an A-CSP, l a level
of xj in P l of local consistency.
We write Rl the set of removals of P w.r.t. l. For any xi ∈ X , any v ∈ D(xi ), v belongs to the alternative
domain of xi iff either v belongs to the domain of xi in the
Let C a constraint in C and t an assignment of vars(C) closure by l consistency of P = (X , D, C ∪H) or (xi 6= v) ∈ Rl
satisfying C. t is said to be invalid w.r.t. l iff there exists and hi is a sufficient justification of (xi 6= v).
xj ∈ 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. The notion of sufficient justification is extended to tuples
as follows:
supports of (x = v)
removals justification vector of each removal t1 t2 t3 t4
x1 6= v1 {h1 , h2 } ? ?
x2 6= v2 {h1 , h3 } ? ?
x3 6= v3 {h2 , h4 } ? ? ?
justification vector {h1 , h2 , h4 } {h1 } {h2 } {h2 , h4 } ∅
Table 2. Computation of the vector of justifications of the removal (x 6= v) on a given constraint C; the ti are the supports of x = v. A
? in cell (ti , xj 6= vj ) means that ti invalid when xj 6= vj
Definition 7 (Sufficient justification of a tuple) Proposition 11
Let P = (X , D, C, H) be an A-CSP, l a level of local consis-
tency, C a constraint in C and t an assignment of vars(C) hi ∈ H is a (1, k)-sufficient justification of (x 6= v) ∈ R(1,k)
satisfying C. iff, for each set V of k variables there exists a support t of
An user choice hi ∈ H is said to be an l- sufficient justifi- x = v on V such as hi is a (1, k)-sufficient justification of t.
cation for t if and only if, for each xj ∈ vars(t), t[xj ] belongs
to the domain of xj in the closure by l consistency of the CSP
3.2 An algorithm of maintenance of the
(X , D, C ∪ H \ {hi }).
alternative domains w.r.t. Arc
Consistency
Example 1 (cont’) If we go back to example 1, once
x1 and x2 have been assigned, tupple (3, 2, 4) is not valid In our application, interactive configuration, the constraint
anymore and has one sufficient justification, h1 (it is enough to be taken into account are mostly table constraints and the
to relax x1 = 1 to make this tupple valid again); remark level of consistency referred to is Generalized Arc Consistency.
that tupple (4, 2, 1), that is also invalid, has no sufficient We thus propose to maintain the alternative domain upon
justification (the relaxation of the two choices is necessary to the assignment of a variable using an extension of GAC4 [15].
make it valid again). Our algorithm propagates not only value removals, but also
justifications: for each removal (xi 6= v), we maintain a vector
Our algorithm is based on the fact that an assignment hi f(xi 6=v) of n boolean flags, one for each choice in H, such that
is an l-sufficient justification for the tuple t if and only if, for f(x6=v) (hi ) = True if and only if hi is a sufficient justification
each xj involved by the tuple, either t[xj ] is in the current of (xi 6= v). According to Proposition 10, f(x6=v) depends on
domain of xj or hi is a sufficient justification of the removal the justifications of the tuples that support (x, v). Hence, we
(xj 6= t[xj ]). Formally, let us call the conflict set of t the set keep, for each tuple t, a bit vector ft such as, for each hi ,
of removals that make it invalid: ft [hi ] is true iff hi is a sufficient justification of t. Intuitively
(see Table 2 for an example), for the user choice hi to be
Definition 8 (Conflict set) a sufficient justification for a removal (x 6= v) provoked by
The conflict set of a tuple t w.r.t. some level of l consis- constraint C, it is needed that the relaxation of hi makes at
tency is the subset of Rl defined by: CS(t) = {(xi 6= v) ∈ least one support t of (x = v) on C valid again, i.e. that all
Rl s. t. t[xi ] = v}. the elements in the conflict set of t have hi as a sufficient
justification (this is the meaning of Proposition 9). In other
Of course, a tuple is invalid if and only if it has a non-empty words, ft is the intersection of the f(xj 6=w) flags of all the
conflict set. removals (xj 6= w) in the conflict set of t. Formally:
Proposition 9 hi is an l-sufficient justification of a tuple Proposition 12
t if and only it is an l-sufficient justification of each of the ^ _ ^
removals in its conflict set w.r.t. l. f(x6=v) = ( ( fr ))
C|x∈vars(C) t∈Support(x,v,C) r∈CS(t)
Finally, it can easily be shown that, when the level local
consistency to maintain is generalized arc consistency: where Support(x, v, C) is the set of assignments of vars(C)
that support (x, v).
Proposition 10 hi is a sufficient justification w.r.t. Arc con-
sistency (GAC) for a removal (x 6= v) iff, for each constraint
C bearing on x, there exists a tuple t support of (x = v) on C We propose here a GAC4 like algorithm, the initialization
such that hi is GAC-sufficient justification of t. and main propagation of which are depicted by algorithms 1
and 2. We use the following notations:
Similar properties can be established for other levels of local
consistency based on the notion of support, typically for k • (X , D, C) is the original CSP, that is supposed arc consis-
inverse consistency [8]3 tent;
3 A CSP is (1, k) consistent iff, for each variable x and each value
• for any constraint C ∈ C, T able(c) is the set of assignments
v in D(x), for each set V of k additional variables, x = v has a of vars(c) that satisfy it. We moreover the tuples involved
support on V, i.e. there exists an assignment t of {x} ∪ V such in the tables are valid (i.e. T able(c) is a subset of the carte-
that for any C ∈ C with vars(C) ⊆ {x} ∪ V, t satisfies C sian product of the domains of the variables its bears on.
• Dc (xi ) is the current domain of xi
• Sxi ,v,C is the set of supports of (xi , v) on C and
Cpt(xi , v, C) is the number of supports of (xi , v) on C.
Procedure Propagate( (xk , w): assumption; (X , D, C): the
• for any tuple t, ft is its vector of justifications; for any
initial CSP; H: the past assumptions; Dc : the current
removal (xi 6= v) f(xi 6=v) is its vector of justifications; for
domains);
any removal (xi 6= v) and any constraint C bearing on xi ,
Add (xk , w) to H;
f(xi 6=v,C) is the vector of justification of (xi 6= v) on C.
Q := ∅;
The difference with GAC4 is that a removal (x 6= v) must /* The removal of the other values in the current domain of xk is
be propagated non only when it is created, but for each change due to hk */
in its vector of justifications. Since the updating of the vectors foreach u 6= w ∈ Dc (xk ) do
of justification is monotonic (a hi might go from being suf- f(xk 6=u) ← Falsem ;
ficient to not, but not the other way around), the algorithm f(xk 6=u) [hk ] ← True;
terminates. More precisely, instead of entering just once in end
Q, each removal can enter in the queue n times at most (n Add (xk 6= u) to Q;
being the number of hi in H), i.e.as much as the number of while Q 6= ∅ do
possible changes in a vector of justifications. The worst case Choose and remove a (xi 6= v) from Q;
complexity is thus bounded by O(nedk ) with e the number of if v ∈ Dc (xi ) then
constraints, m the number of variables, n the maximal num- Remove v from Dc (xi );
ber of assumptions (typically, n = m), d the maximum size end
of the domains and k the maximum arity of constraints. It is foreach C s.t. xi ∈ vars(C) and each tuple t in
thus the same complexity as the GAC-4 based naive method: Si,v,C do
M em ← ft ;
n.O(e.dk ). With the important difference that in the naive
ft ← ft ∧ f(xi 6=v) ;
method, GAC-4 is called exactly n times while n is a worst
if valid(t) then
case bound for justification-based algorithm.
foreach xj ∈ vars(t) s.t. j 6= i do
Concerning space complexity, GAC4 memorizes the sup-
Cpt(xj , t[xj ], C)−− ;
port Si,v,C for each xi , each value v in its domain and each
if Cpt(xj , t[xj ], C) == 0 then
constraint C bearing on xi ; Let say that this structure is in f(xj 6=t[xj ]),C ← Falsem /* init; will be
O(T ) ( T is actually proportional to the space taken by valid computed later */ ;
tuples in constraint tables). Our algorithm also maintains, for Add (xj 6= t[xj ]) to Q;
each tuple t, a vector of n flags, meaning a O(T.n) space. For if t[xj ] ∈ Dc (xj ) then
each removal and each constraint bearing on the variable of f(xj 6=t[xj ]) ← Truem /* init */ ;
the removal, we also keep a vector of n boolean flags. Since end
the number of removals is bounded by the number of vari-
end
able/value pairs (xi , v) in the problem, the algorithm involves
end
in the worst case as many boolean vectors as the number of
valid(t) = f alse;
Si,v,C sets used by GAC4; Hence a global a spatial consump-
end
tion bounded by O(n.T ).
if M em! = ft /* A justif. of t is not sufficient
anymore */ then
Procedure Initialize((X , D, C):CSP; n: integer)
/* (X , D, C) is the original CSP assumed to be arc consistent */
foreach xj ∈ vars(t) s.t. j 6= i do
mem0 = f(xj 6=t[xj ]) ;
/* All the tuples are supposed to be valid */
f(xj 6=t[xj ]),C = f(xj 6=t[xj ]),C ∨ ft ;
/* n is the maximal number of assumptions to be considered */
fxj 6=t[xj ] = fxj 6=t[xj ] ∧ fxj 6=t[xj ],C ;
begin
foreach C ∈ C do if mem0 6= f(xj 6=t[xj ]) then
foreach xi ∈ vars(C), v ∈ D(xi ) do Add (xj 6= t[xj ]) to Q;
Cpt(xi , v, C) := 0; end
Si,v,C = ∅ end
end end
foreach t ∈ T able(C) do end
ft = Truen ; end
valid(t) = True; foreach hi ∈ H do
CS(t) = Falsen ; Dalt (xi ) = ∅; foreach v ∈ Dxi do
foreach xi ∈ vars(C) do if f( xi 6= v)[hi ] then
Cpt(xi , t[xi ], C) + +; Add v to Dalt (xi )
Add t to Si,t[xi ],C end
end end
end end
end Algorithm 2: Propagation of decision hk = (xk ← w)
end
Algorithm 1: Initialization
4 First experimental results domains to be computed, our approach keeps limited justifi-
cations of the removals. Tested on two industrial benchmarks,
We have tested this algorithm on an industrial prob- this method quickly outperforms the naive method.
lem of configuration. It involves 32 variables of domain The main limitation of our method is obviously its space
of size 2 to 10, 35 binary constraints. The product to consumption; the extra space consumption depends directly
configure is a blowing machine, which blows bottles for of the number of variables for which we want to compute
different matters. The benchark can be found at url the alternative domain. This being said, it should be kept in
ftp://ftp.irit.fr/pub/IRIT/ADRIA/PapersFargier/Config/souffleuse.xml. mind that for practical purposes the system is not asked to
The protocol simulates 1000 sessions of configurations as display all the alternative domains; the human user has with
follows. First, a sample of 1000 consistent complete assign- a limited mental capacity and it is not obvious that she can or
ments is randomly fired. For each of then, the corresponding even wants to see a lot of alternative domains at a glance. In a
session is simulated by assigning the variables following a ran- configuration application for instance, the user looks at only
dom (uniform) order. After each assignment, we measure the a small number of variable simultaneously, typically the ones
cpu time needed to make the current problem arc-consistent involved in the subcomponent currently being configured.
and to compute the alternative domains of all the already The concepts we have coined are close to the notion of value
assigned variables are computed. The whole protocol is ap- restoration. In the current work, we focused on the computa-
plied by both the justification-based algorithm described in tion of alternative domains; an alternative value is a forbidden
the previous Section and the naive method (that works on as value that can be restored by the sole relaxation of the assign-
may copies of the original CSP as the number of user choices ment of its variable. But more generally any value having at
in H, as decribed in introduction of Section 3 ) ; for the shake least one sufficient justification can be restored by the relax-
of rigor, the two algorithms play on the same assignments and ation of only one assignment. For each value in the domain of
the same assignment orders. an assigned variable, the user knows whether she can change
Figure 1 presents the result of these experiments. On the her choice to this value without modifying the other choices -
x-axis is the number of the assignment in the sequence; the this is the notion alternative domain. But the user also knows
y-axis is logarithmic and indicates the mean cpu time need something about the values that have been filtered from the
for the naive method (plain line, with rounds) and for the domains of the unassigned variables: the justification vector
justification-based algorithm dotted line, with squares. 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 pro-
posed 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 per-
spectives. Firstly, our algorithm obviously needs to be im-
proved, 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 con-
straints ; such an algorithm is not too difficult to conceive for
CSPs involving binary constraints only, but the task seems
Figure 1. Computation time required by both the naive
method and the justification-based algorithm (logarithmic scale). 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
The results are quite good: our algorithm is faster as soon might mean an hybridizing with the maintenance algorithms
as more than 5 variables are assigned, i.e.when more than of propagation/depropagation in dynamic CSP[2, 3, 6].
5 alternative domains are to be computed. As expected, the
time required by the naive algorithm grows linearly with the ACKNOWLEDGEMENTS
number of variables, while our algorithm has stable computa-
tion time. These first results have obviously to be confirmed This work is partially funded by the ANR project BR4CP
by more experiments on bigger configuration problems. (ANR-11-BS02-008)
5 Conclusion REFERENCES
[1] Jérôme Amilhastre, Hélène Fargier, and Pierre Marquis, ‘Con-
In this work, we have coined the new concept of the alternative sistency restoration and explanations in dynamic csps appli-
domain of a variable with respect to a local consistency level cation to configuration’, Artificial Intelligence, 135(1-2), 199–
and proposed an extension of GAC4 algorithm as a way to 234, (2002).
compute the alternative domains when maintaining General [2] Christian Bessière, ‘Arc-consistency for non-binary dynamic
csps’, in Proceedings of ECAI’92, pp. 23–27, (1992).
Arc Consistency on problems involving table constraints. [3] Romuald Debruyne, ‘Arc-consistency in dynamic csps is no
Contrarily to the naive method that applies the propaga- more prohibitive’, in Proceedings of ICTAI’96, pp. 299–307,
tion algorithm as many times as the number of alternative (1996).
[4] Romuald Debruyne, ‘A property of path inverse consis- Pil , which is a contradiction.
tency leading to an optimal pic algorithm’, in Proceedings
of ECAI’2000, pp. 88–92, (2000).
[5] Romuald Debruyne and Christian Bessière, ‘Some practicable ⇐ Reciprocally, let hi be an l-sufficient justification of
filtering techniques for the constraint satisfaction problem’, in all the removals in the conflict set of t. For each of these
Proceedings of IJCAI’97, pp. 412–417, (1997). (xj 6= vj ), vj is by definition in the domain of xj in Pil .
[6] Romuald Debruyne, Gérard Ferrand, Narendra Jussien, Thus, t is a valid tuple in Pil - by definition of the notion of
Willy Lesaint, Samir Ouis, and Alexandre Tessier, ‘Correct-
ness of constraint retraction algorithms’, in Proceedings of
justification, hi is thus an l-sufficient justification of t. 2
FLAIRS’03, pp. 172–176, (2003).
[7] Gerhard Fleischanderl, Gerhard Friedrich, Alois Haselböck, [Proof of Proposition 10]
Herwig Schreiner, and Markus Stumptner, ‘Configuring large ⇒ Let hi be a GAC sufficient justification of a removal
systems using generative constraint satisfaction’, IEEE Intel- (x 6= v) . Suppose that there exits a constraint C bearing on
ligent Systems, 13(4), 59–68, (1998).
[8] Eugene C. Freuder, ‘A sufficient condition for backtrack- x such that none of the supports of x = v on C admits hi
bounded search’, Journal of the ACM, 32(4), 755–761, as a sufficient justification. This means that these tuples are
(1985). not valid in the arc consistent closure of (X , D, C ∪ H \ {hi })
[9] Eugene C. Freuder and Charles D. Elfe, ‘Neighborhood in- (denoted PiGAC ). Thus v has no support on C in PiGAC : it
verse consistency preprocessing’, in Proceedings of AAAI’96,
pp. 202–208, (1996).
does not belongs to the domain of x in PiGAC ; hi is thus not
[10] Ester Gelle and Rainer Weigel, ‘Interactive configuration a sufficient justification of (x 6= v) .
using constraint satisfaction techniques’, in Proceedings of
PACT-96, pp. 37–44, (1996). ⇐ Reciprocally, consider an assumption hi and suppose
[11] Emmanuel Hebrard, Brahim Hnich, and Toby Walsh, ‘Su- that ∀C bearing x, ∃t support of x = v such that hi is a
per solutions in constraint programming’, in Proceedings of
CPAIO’04, pp. 157–172, (2004). GAC sufficient justification of t . This means that, for any
[12] Daniel Mailharro, ‘A classification and constraint-based constraint bearing on x there exists a support t of x = v valid
framework for configuration’, Artificial Intelligence for En- in PiGAC ; v thus belongs to the domain of x in PiGAC - by
gineering Design, Analysis and Manufacturing, 12, 383–397, definition, this meant that hi is a GAC-sufficient justification
(September 1998).
[13] Sanjay Mittal and B. Falkenhainer, ‘Dynamic constraint sat-
of (x 6= v). 2
isfaction problems’, in Proceedings of AAAI’90, pp. 25–32,
(1990). [Proof of Proposition 11]
[14] Sanjay Mittal and Felix Frayman, ‘Towards a generic model ∀(x1 , ..., xk ), ∃(v1 , ..., vk ) a support of x = v such that hi is a
of configuraton tasks’, in Proceedings of the IJCAI’89, pp. (1, k)-sufficient justification of (v1 , ..., vk )
1395–1401, (1989).
[15] Roger Mohr and Gérald Masini, ‘Good old discrete relax-
ation’, in Proceedings of the ECAI’88, pp. 651–656, (1988). ⇔ ∀(x1 , ..., xk ), ∃(v1 , ..., vk ) support of x = v such that any
[16] Samir Ouis, Narendra Jussien, and Olivier Lhomme, ‘Expli- of the vj belongs to the domain of its variable in the closure
cations conviviales pour la programmation par contraintes’, by (1, k)-consistency of (X , D, C ∪ H \ {hi })
in Actes de JFPLC, pp. 105–118, (2002).
[17] Daniel Sabin and Eugene C. Freuder, ‘Configuration as com-
posite constraint satisfaction’, in AI and Manufacturing Re- ⇔ v belongs to the domain of x the closure by (1, k)-
search Planning Workshop, pp. 153–161, (1996). consistency of (X , D, C ∪ H \ {hi }) (definition of the 1, k
[18] Daniel Sabin and Rainer Weigel, ‘Product configuration consistency)
frameworks — a survey’, IEEE Intelligent Systems, 13(4), ⇔ hi is a justification (1, k)-sufficient of x 6= v. 2
42–49, (1998).
[19] Markus Stumptner, Gerhard E. Friedrich, and Alois
Haselböck, ‘Generative constraint-based configuration of [Proof of Proposition 12]
large technical systems’, AI EDAM, 12(04), 307–320, (1998). According to Proposition 10, when GAC is ensured
[20] Junker Ulrich, ‘Configuration’, in Handbook of Constraint
Programming, 837–874, Elsevier Science, (2006).
^ _
f(x6=v) [hi ] = ft [hi ]
[21] Rainer Weigel and Christian Bliek, ‘On reformulation of con-
straint satisfaction problems’, in Proceedings of ECAI’98, pp. C,x∈vars(C) t∈Support(x,v,C)
254–258, (1998).
For any hi , any x ∈ X and any v ∈ Dx . I.e.:
^ _
A Proofs f(x6=v) = ft
C,x=vars(C) t∈Support(x,v,C)
[Proof of Proposition 9]
Of course, the proposition holds when t is valid (it has an Yet, according to Proposition 9, the GAC-sufficient justifica-
empty conflict set). Let us examine the case of an invalid tions set of a tuple is the intersection of GAC-sufficient justifi-
tuple.
V
cations of the removals from its conflict set: ft = r∈CS(t) fr .
Hence the result. 2
⇒ Let hi be l-sufficient justification of an invalid tuple
t and suppose that there exists a removal (x 6= v) in the
conflict set of t such that hi is not a sufficient justification of
(x 6= v).
We write Pil the l-consistent closure of (X , D, C ∪ H \ {hi }).
Since hi is an l-sufficient justification of t, by definition, t is
valid in Pil . Since hi is also not a sufficient justification of
(x 6= v), v is not in the domain of x in Pil ; t is thus invalid in