Maintaining Alternative Values in Constraint-Based Configuration

1 Introduction

The Constraint Satisfaction Problem (CSP) formalism offers a powerful framework for representing a great variety of problems, e.g. routing problems, resource allocation, frequency assignment, configuration 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 difficult 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 efficient complete algorithms) or getting around (studying the polynomial subclasses or proposing incomplete algorithms).

∗This work is partially funded by the ANR project "Business Recommendation for Configurable Products" (BR4CP), ANR-11BS02-008

H´el`ene Fargier

IRIT - University of Toulouse France fargier@irit.fr

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 configuration [Mittal and Frayman, 1989; Sabin and Weigel, 1998; Mailharro, 1998; Stumptner et al., 1998; Junker, 2006] is a typical example of such problems: a configurable product is defined by a finite set of 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 finite set of 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 definition of a catalog or a range of products, and more specifically the definition of configurable products. These extensions have been motivated by difficulties and characteristics that are specific to the modeling and the handling of catalogs of configurable products. Dynamic CSPs [Mittal and Falkenhainer, 1990], for instance suit problems where the existence of some optional variables depends on the values of some other variables. Other extensions proposed by the CSP community include composite CSPs [Sabin and Freuder, 1996], interactive CSPs [Gelle and Weigel, 1996], hypothesis CSPs [Amilhastre et al., 2002], generative constraint satisfaction [Stumptner et al., 1998; Fleischanderl et al., 1998], etc.

In this paper, we do not deal with such representation problems: we assume that the product range is specified by a classical CSP. Instead, our work focuses on the human-computer interaction. When configuring a product, the user specifies her requirements by interactively giving values to variables. Each time a new choice is made, the domains of the further variables must be pruned so as to ensure that the values available in their domains can lead to a feasible product (i.e., a product satisfying all the initial configuration constraints): the aim of the system is to keep the domains of the other variables consistent with these choices. Since maintaining the global inverse consistency is generally not tractable, the domains are rather filtered 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 ones of the assigned variable without leading to the violation of some constraint.

The structure of the present article is as follows: the problematics of alternative domains is described in the next Section. Section 3 then develops the basis of our algorithm. Our first experimental results are shown in Section 4. Proofs are omitted for the sake of brevity 1 .

2 Background and Problematics

A CSP is classically defined by a triplet (X , D, C) where X = {x1, . . . , xm} is a finite set of m variables, each xi taking its values in a finite domain D(xi), and a finite set of constraints C. We note D = ∏nj=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 ∈ Y we denote by t[xj] the value assigned to xj in t.

A constraint C in C involves a set vars(C) ⊆ X and can be viewed as a function from the set of assignments of vars(C) 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 of vars(C) is a support of this value (more precisely, of (xj, v) on C) iff t[xj] = v and t satisfies C.

An assignment t of X is a solution of the CSP iff it satisfies all the constraints. If such a solution exists, the CSP is said to be consistent, otherwise it is inconsistent.

Formally, a configurable product is represented as a CSP (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 xi. Following [Amilhastre et al., 2002], the problem can be represented by an Assumption-based CSP (A-CSP).

Definition 1 (A-CSP) An A-CSP is a 4-tuple (X,D, C,H) where (X , D, C) is a CSP and H a finite set of constraints on variables of X .

In configuration, H represents the current user choices, i.e. assignments of the variables: we suppose in the sequel that all the restrictions in H bear with different variables and restrict their domains to a unique value 2 ; we will denote by hi = (xi ← v) the restriction fromH on xi, if it exists.

After each choice, the system filters 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) iff, for any variable xj ∈ 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 first one (i.e. having the same set of solutions) and arc consistent; this problem is called the closure by arc consistency of the first one.

1 A full-proof version of the paper is available at ftp://ftp.irit.fr/ IRIT/ADRIA/ijcai13BF.pdf

2 Actually, the definitions and results could be set in a more general framework and capture any type of restriction, and in particular restrictions of the form "xi ∈ A" or "xi ̸= v"; the meaning of alternative values when the restrictions in H bear on more than one variable is nevertheless questionable, hence our assumption.

Other, more powerful, levels of local consistency can be ensured, e.g. Path Inverse Consistency [Debruyne, 2000], Singleton Arc Consistency [Debruyne and Bessi`ere, 1997], kinverse consistency [Freuder, 1985; Freuder and Elfe, 1996]. In the following definitions, we do not make any assumption on the level of local consistency that is ensured. We simply consider that, after each choice, an algorithm is called that ensures some level a of local consistency - i.e. that computes the closure by a consistency of the original problem. We call the current domain of a variable its domain in this closure.

Definition 2 (Current domain of a variable) Let a be a level of local consistency and P = (X,D, C,H) an ACSP. The current domain according to a-consistency of a variable xi is its domain in the closure by a-consistency of (X , D, C ∪ H).

We can now formally define the notion of alternative domain of an assigned variable as the current domain that it would have if the user would take this assignment back:

Definition 3 (Alternative domain) Let a be a level of local consistency and P = (X , D, C, H) an A-CSP. The alternative domain of a variable xi according to a is its domain in the closure by a-consistency of the CSP(X,D, C ∪ H \ {hi}). We write it Da alt (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 to another value than v and (ii) the single relaxation of this assignment would make v a-consistent. For instance, if xi is the last assigned variable, all the values that were in the domain of xi just before this assignment are alternative values. An example of alternative domain can be seen on Table 1. Notice that alternative values are generally not interchangeable in the full sense [Freuder, 1991] with assigned values (nor with each other): it is possible that only one of theses values belongs to a solution. Alternative values are alternatives w.r.t the level of local consistency considered. Notice also that the previous definition theoretically applies to any level of local consistency, but its application is actually restricted to local consistencies that remove values from the domains.

The notion of alternative domain is orthogonal to the notion of removal's explanation, such as proposed in PaLM [Jussien and Ouis, 2001; Jussien and Barichard, 2000]: explanations are a way to explain the pruning of the domains and aim at proposing a strategy of restoration of some values for an unassigned variable by the relaxation of a (minimal) subset of user's choices. On the contrary, the alternative domain of a variable provides a way to change the value of an assigned variable without any modification of her other choices.

The notion of alternative domain can be compared to the concept of (1, 0)-super-solution proposed by Hebrard et al. [Hebrard et al., 2004]. An (a, b)-super-solution is a solution of the CSP such that, if a variables lose their values, it can be repaired by assigning these variables with new values and modifying the values of at most b other variables. It is a generalization of the notion of fault tolerant solution [Weigel and Bliek, 1998], a fault tolerant solution being a (1, 0)-supersolution. A fault tolerant solution is actually a solution such as all the variables have a non-empty alternative domain: if one of the current values in the assignment is made unavailable for any reason, a solution can still be found by choosing a value from its alternative domain - this value is by definition compatible with the other choices. Formally,

Proposition 1 Let d be a solution of a CSP (X , D, C) and let H = {hi = (xi ← d[xi]), i = 1, . . . , card(X)}. d is a (1, 0)-super-solution of (X,D, C) if and only if, ∀xi ∈ X, the alternative domain of xi according to arc-consistency is a strict superset of {d[xi]}.

The main difference between (1, 0) super-solutions and alternative domains is that super-solutions deal with complete assignments while alternative domains suggest restoration values even for partial assignments. Technically, this implies that algorithms computing super-solutions that are based on variable duplication do not work for the computation of alternative domains, as shown in Figure 1. In this example, x′i denotes the duplicates of the original variables xi; consider that the user has chosen x1 ← 1 and x2 ← 2, the arcconsistency filtering reduces the domain of x3 to {3}; the domain of x′1 , which were supposed to hold the alternative values of x1, thus becomes empty, while 3 still belongs to the alternative domain of x1.

We can finally notice that the two notions target different practical goals: when refereing to a super-solution, we are looking for some, but not all, robust (and complete) solutions - there is indeed a potentially exponential number of super-solutions. When computing alternative domains, we are looking for all the alternative values, and this even during the search, when the assignments are partial.

3 Computing alternative domains

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 variable xi which remains unassigned in Pi. Each Pi is filtered by a-consistency. The alternative domain of variable xi in 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. It will be the reference point from our method, which follows the opposite philosophy: memorizing information in order to avoid a duplicate work.

3.1 Removals and sufficient justifications

The main idea of our approach is to maintain, for each value removed by the filtering algorithm, a vector of boolean flags, one flag for each hi ∈ H. The flag 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:

Definition 4 (Removal, invalid tuple) Let P = (X,D, C,H) be an A-CSP and P a the closure of (X,D, C ∪H) by some level of local consistency a.

A removal w.r.t. a is a pair (xj, v), xj ∈ X, v ∈ D(xj) such that v does not belong to the domain of xj in P a We write Ra the set of removals of P w.r.t. a.

Let C be a constraint in C and t an assignment of vars(C) satisfying C. t is said to be invalid w.r.t. a iff there exists xj ∈ vars(C) such that t[xj] does not belong to domain of xj in P a ; otherwise, it is said to be valid w.r.t. a.

To improve readability, a removal (xj , v) will often be written (xj ̸= v), and we will omit to mention level a of local consistency to which the removal refers when not ambiguous.

Definition 5 (Sufficient Justification of a removal) Let

P = (X,D, C,H) be an A-CSP, a a level of local consistency, and Ra the P ′ s removals according to a.

For any xj in X and any v in D(xj), hi ∈ H is said to be an a-sufficient justification of v for xj if and only if v belongs to the domain of xj in the a-consistent closure of (X , D, C ∪ H \ {hi}).

For instance, if the propagation of the last assignment leads to the removal of the value v in the domain of x, this assignment is a sufficient justification of x ̸= v. By extension, any hi is a sufficient justification of a value that does belong to the current domain of its variable. Of course:

Proposition 2 Let P = (X, D, C,H) be an A-CSP, a a level of local consistency.

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 closure by a consistency of P = (X,D, C ∪ H) or (xi ̸= v) ∈ Ra and hi is a sufficient justification of (xi ̸= v).

The notion of sufficient justification extends to tuples:

Definition 6 (Sufficient justification of a tuple) Let P = (X , D, C, H) be an A-CSP, a a level of local consistency, C a constraint in C and t an assignment of vars(C) satisfying C.

A user choice hi ∈ H is said to be an a- sufficient justification for t if and only if, for each xj ∈ vars(t), t[xj] belongs to the domain of xj in the closure by a consistency of the CSP (X , D, C ∪ H \ {hi}).

Our algorithm is based on the fact that an assignment hi is an a-sufficient justification 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 sufficient justification of the removal (xj ̸= t[xj]). Formally, let us call the conflict set of t the set of removals that make it invalid:

Definition 7 (Conflict set)

The conflict set of a tuple t w.r.t. some level of a consistency is the subset of Ra defined by: CS(t) = {(xi ̸= v) ∈ Ra s. t. t[xi] = v}.

Of course, a tuple is invalid iff it has a non-empty conflict set.

Proposition 3 hi is an a-sufficient justification of a tuple t if and only it is an a-sufficient justification of each of the removals in its conflict set w.r.t. a.

Finally, it can easily be shown that, when the level of local consistency to be maintained is generalized arc consistency:

Proposition 4 hi is a sufficient justification w.r.t. Arc consistency (GAC) for a removal (x ̸= v) iff, for each constraint C bearing on x, there exists a tuple t support of (x = v) on C such that hi is a GAC-sufficient justification of t.

Similar properties can be established for other levels of local consistency based on the notion of support, e.g. for k inverse consistency [Freuder, 1985] 3 .

3 A CSP is (1, k) consistent iff, for each variable x and each value v in D(x), for each set V of k additional variables, x = v has a support on V, i.e. there exists an assignment t of {x} ∪ V such that for any C ∈ C with vars(C) ⊆ {x} ∪ V, t satisfies C.

Proposition 5 hi ∈ H is a (1, k)-sufficient justification of (x ̸= v) ∈ R(1,k) iff, for each set V of k variables there exists a support t of x = v on V such as hi is a (1, k)-sufficient justification of t.

3.2 An algorithm for maintaining the alternative domains w.r.t. Arc Consistency

In our application, interactive configuration, the constraints to be taken into account are mostly table constraints and the level of consistency referred to is Generalized Arc Consistency. We propose to maintain the alternative domain upon the assignment of a variable using an extension of GAC4 [Mohr and Masini, 1988]. Our algorithm propagates not only value removals, but also justifications: for each removal (xi ̸= v), we maintain a vector f(xi̸=v) of n boolean flags, one for each choice in H, such that f(x̸=v)(hi) = True if and only if hi is a sufficient justification of (xi ̸= v). According to Proposition 4, f(x̸=v) depends on the justifications of the tuples that support (x, v). Hence, we keep, for each tuple t, a bit vector ft such as, for each hi, 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 a sufficient justification for a removal (x ̸= v) provoked by constraint C, it is needed that the relaxation of hi makes at least one support t of (x = v) on C valid again, i.e. that all the elements in the conflict set of t have hi as a sufficient justification (this is the meaning of Proposition 3). In other words, ft is the intersection of the f(xj̸=w) flags of all the removals (xj ̸= w) in the conflict set of t. Formally:

Proposition 6 Let Support(x, v, C) is the set of assignments of vars(C) that support (x, v); it holds that

We propose here a GAC4 like algorithm, the initialization and main propagation of which are depicted by Algorithms 1 and 2. We use the following notations:

• (X,D, C) is the original CSP, that is supposed to be arc consistent;
• Table(C) is the assignments of vars(c) that satisfy C. Moreover the tuples involved in the tables are valid (i.e. Table(c) is a subset of the cartesian 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.
• ft is the vector of justifications of tuple t; f(xi̸=v) is the vector of justifications of removal (xi ̸= v); for any removal (xi ̸= v) and any constraint C bearing on xi, f(xi̸=v,C) is the vector of justification of (xi ̸= v) on C.

The difference with GAC4 is that a removal (x ̸= v) must be propagated not only when it is created, but every time its vector of justifications changes. Since updating the vectors of justification is monotonic (an hi might go from being sufficient to not, but not the other way around), the algorithm terminates. More precisely, instead of entering just once in Q,

Algorithm 1: Initialization

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 ∈ C do foreach xi ∈ vars(C), v ∈ D(xi) do Cpt(xi, v, C) ← 0; Si,v,C ← ∅ foreach t ∈ Table(C) do ft ← Truen ; valid(t) ← True; CS(t) ← Falsen ; foreach xi ∈ vars(C) do Cpt(xi, t[xi], C) + +; Add t to Si,t[xi],C

each removal can enter in the queue n times at most (n being the number of hi in H), i.e.as many times as the number of possible changes in a vector of justifications. 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 difference that in the naive method, GAC-4 is called exactly n times while n is a worst case bound for justification-based algorithm.

Concerning space complexity, GAC4 memorizes the support 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 flags, 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 flags. 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 Si,v,C sets used by GAC4; Hence a global a spatial consumption bounded by O(n.T ).

4 Experimental results

We have tested this algorithm on three industrial problems of car configuration 4 . The names and values have been banalized for confidentiality reasons - we call these problems Small, Medium and Big.

• Small : 139 variables, domain sizes from 2 to 16, 147 constraints of arity 2 to 6 (68Ko, a total of 3.041 tuples).

4 These instances have been built in collaboration with the car manufacturer Renault; see [Astesana et al., 2013] for a more detailled description.

Procedure Propagate( (xk,w): assumption; (X,D, C): the 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 ̸= w ∈ Dc(xk) do f(xk̸=u) ← Falsem; f(xk̸=u)[hk] ← True; Add (xk ̸= u) to Q; while Q ̸= ∅ do Choose and remove an (xi ̸= v) from Q; if v ∈ Dc(xi) then Remove v fromDc(xi); foreach C s.t. xi ∈ vars(C) and each tuple t in Si,v,C do Mem ← ft; ft ← ft ∧ f(xi̸=v); if valid(t) then foreach xj ∈ vars(t) s.t. j ̸= i do Cpt(xj , t[xj ], C)--; if Cpt(xj, t[xj], C) == 0 then f(xj̸=t[xj]),C ← Falsem /* init; will be computed later */ ; Add (xj ̸= t[xj]) to Q; if t[xj] ∈ Dc(xj) then f(xj̸=t[xj]) ←Truem /* init */ ; valid(t) ← f alse; if Mem! = ft /* A justif. of t is not sufficient anymore */ then foreach xj ∈ vars(t) s.t. j ̸= i do mem′ ← f(xj ̸=t[xj ]); f(xj ̸=t[xj ]),C ← f(xj ̸=t[xj ]),C ∨ ft; fxj ̸=t[xj ] ← fxj ̸=t[xj ] ∧ fxj ̸=t[xj ],C ; if mem′ ̸= f(xj̸=t[xj]) then Add (xj ̸= t[xj]) to Q; foreach hi ∈ H do Dalt (xi) ← ∅; foreach v ∈ Dxi do if f(xi ̸= v)[hi] then Add v to Dalt (xi)

• Medium : 148 variables, domain sizes from 2 to 20, 174 constraints of arity 2 to 10 (185Ko, 9.531 tuples).
• Big : 268 variables, domain sizes from 2 to 324, 332 constraints of arity 2 to 12 (3.57M, 225.982 tuples).

The protocol simulates 500 sessions of configurations as follows. First, a sample of 500 complete and consistent assignments is randomly built. For each of them, 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 assigned variables. The whole protocol is applied by both algorithms, which play on the same assignments with the same assignment orders. Figure 2 presents the result of these experiments on a HP Z600 workstation (Intel Xeon X5650 2.66Ghz processor, 16Gb Mb of RAM). On the xaxis is the number of the assignment in the sequence; the y-axis the mean cpu time needed for the naive method (dotted blue line) and for the justification-based algorithm dotted line (plain black line). We also measured the cpu used for a simple run of GAC4 (without maintaining any alternative domain) on the same protocol. For the first assignment, GAC4 -without the initialization step - takes a max of 0.003s (average 0.001s); for the next assignments, a max of 0.001s (average about 0.0005; the higher the number of past assignments, the lower the number of propagations).

The results are quite good: our algorithm is faster after the first 3 (resp. 5, resp. 15) variables have been assigned, i.e.when more than 3 (resp. 5, resp. 15) alternative domains are to be computed. Unsurprisingly, the first assignments are more costly, because of the initialisation of the structure - anyway, except for the first variable in the Big instance, the cpu is always lower than one second ; recall that Big is really big: its table constraints involve a total of 225.982 tuples. As expected, the time required by the naive algorithm grows linearly with the number of assigned variables, while our algorithm has a decreasing computation time.

5 Conclusion

In this work, we have coined the new concept of alternative domain of a variable and proposed an extension of GAC4 as a way to compute the alternative domains when maintaining General Arc Consistency on CSP with table constraints. Contrarily to the naive method that calls the propagation algorithm as many times as the number of alternative domains to be computed, our approach keeps limited justifications of the removals. Tested on 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 a limited cognitive load and it is not obvious that she can or even wants to see a lot of alternative domains at a glance. In a configuration application for instance, the user looks at only a small number of variable simultaneously, typically the ones involved in the subcomponent currently being configured.

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 sufficient justification can be restored by the relaxation of only one assignment (if the variable is not assigned, by the relaxation of another one variable assignment). 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 great 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 domains in CSP with general constraints, and not just in table constraints (actually, the GAC4-based approach does apply for intentional constraints, but would be too heavy: in the worst case, it would lead to generate the tables corresponding to the constraints). Finally, we should be able to consider the whole interaction; in this paper, we have considered only the assignment of a value to a variable: we need to study also the relaxation of these choices. This adaptation might mean an hybridizing with some algorithms of propagation/depropagation in dynamic CSP, e.g. the ones proposed by [Bessi`ere, 1992; Debruyne, 1996; Debruyne et al., 2003].