=Paper=
{{Paper
|id=Vol-1453/13_Haag_ArcConsistencyWithNegative_Confws-15_p81
|storemode=property
|title=Arc consistency with negative variant tables
|pdfUrl=https://ceur-ws.org/Vol-1453/13_Haag_ArcConsistencyWithNegative_Confws-15_p81.pdf
|volume=Vol-1453
|dblpUrl=https://dblp.org/rec/conf/confws/Haag15
}}
==Arc consistency with negative variant tables==
https://ceur-ws.org/Vol-1453/13_Haag_ArcConsistencyWithNegative_Confws-15_p81.pdf
Arc Consistency with Negative Variant Tables
Albert Haag1
Abstract. In this paper I discuss a fundamental difference between
Table 1. Variant table for a simple configurable t-shirt
positive and negative variant tables (tables listing excluded combi-
nations) from the viewpoint of a modeler. I provide an approach to
achieving arc consistency with negative tables that can be integrated Color Size Print
Black Small MIB
into an existing configurator that already implements methods for Black Medium MIB
arc consistency. I also provide a simple necessary condition to test Black Large MIB
whether a further restriction of given domains is possible using a neg- Black Medium STW
ative table. As a positive table is equivalent to a negative table repre- Black Large STW
Red Medium STW
senting the complement, this condition test also applies for positive
Red Large STW
tables that have a small complement. I refer to this process as double White Medium STW
negation. A prototypical implementation in Java exists that covers White Large STW
the work described both here and in [6]. I present aggregated results Blue Medium STW
of applying double negation to variant tables from real product test Blue Large STW
data in [6]. This also validates the overall functional correctness of
the entire approach.
2. The persons maintaining the table are expressing exclusions com-
pletely independently of any thought of what the affected property
1 Introduction domains might be.
Tabular data are an important element of product configuration mod-
els. In the context of the SAP Variant Configurator - SAP VC [3] a One obvious way of dealing with negative variant tables that per-
table that lists valid combinations of product properties is referred to tains to the first case is to provide support for complementing the ta-
as a variant table. The number of columns of a variant table is called ble with respect to global domains of the product properties at main-
its arity. Each column of the table is mapped to a product property, tenance time5 . Note that it is not possible to calculate the complement
e.g., Color. to the global domains if these are unconstrained6 .
The simplest form of a product model is just as one single variant I shall focus on the second case as requests by SAP customers
table. The term variant table derives from this. Table 1, below is clearly indicate this setting. Then, it is not legal to complement a
an example of a variant table that completely describes the model negative table at maintenance time with regard to the global domains
of a configurable t-shirt by listing all variants. The t-shirt has three even if these are finite, because they may change after the table was
properties Color, Size, and Print2 . Given the values that appear in maintained. The table may have its own update cycle and should,
the table3 it is evident that 11 of possible 24 combinations have been therefore, not need to be touched each time a global domain changes.
selected as valid for configuration. I expand on this model in Section In knowledge-based configuration variant tables function as table
3. constraints. The extensional form of a table constraint (explicitly list-
Now, SAP customers have long requested the ability to also main- ing all tuples of values implied by the table) closely corresponds to
tain tables of disallowed (excluded) combinations of product proper- the relational form of a variant table (directly storing the variant ta-
ties. These would be called negative variant tables. ble transparently in a relational database7 ). Each value aij (where i
Whereas, a positive table implicitly defines a bound on the overall is the index of the row, and j is the index of the column) that occurs
(global) domains of the associated properties4 , this is different for a in a table cell states a Boolean proposition pij that the corresponding
negative variant table. There are at least two interpretations of the mapped property vj is assigned to that value (pij |= (vj = aij )).
motivation for maintaining a negative table: In this case, a row ri in the variant table directly maps to a tuple
of propositions τi in the associated table constraint representing the
1. The persons maintaining a negative table are aware of overall
(global) domains for the affected product properties. The negative 5 If the challenge lies in the large size of the positive variant table, offering
form of the table is merely chosen as shorthand for maintaining maintenance of the table directly in a compressed format is another option.
the complement of an otherwise very large positive table. Compressions of Table 1 are depicted in [6]. For the SAP VC some support
is provided for complementing tables at maintenance time and maintain-
1 SAP SE, Germany, email: albert.haag@t-online.de
ing tables in non-extensional form, i.e., with cells containing non-atomic
2 The example is taken from [1]. I use and extend it both here and in [6] entities such as real-valued intervals or sets of values
3 I have kept the shorthand codes of M IB (for “Men in Black”) and ST W 6 Unconstrained domains are not that common in traditional business settings,
(for “Save the Whales”) used in [1] but they do occur. For real-valued numeric properties the global domains
4 That is to say, for a positive table a value that does not occur in a particular may often be (bounded/unbounded) continuous intervals
table column can be removed from the domain of the property associated 7 In this case, the table cells will contain only atomic values (Strings or num-
with that column bers)
81 Juha Tiihonen, Andreas Falkner, and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
conjunction of its elements, i.e., for fixed row index i and arity k at run-time. It is important that run-time operations do not impede
ri = (ai1 , . . . , aik ) and τi = (pi1 , . . . , pik ) |= pi1 ∧ . . . ∧ pik . the overall performance of the configurator. Maintenance-time oper-
A central form of constraint evaluation is propagation to achieve ations should be performant as well, but this is less critical.
arc consistency, which removes any values from the current domains In Section 2, I introduce the notation and some formalisms. Sec-
of the properties constrained by the variant table that are not sup- tion 3 uses the product model of a t-shirt taken from [1] (Table 1) to
ported in the intersection of the table with these domains. This is a illustrate the concepts. As already mentioned, Sections 4 and 5 deal
proven way in practice to limit the choices available to the user in with deriving the necessary condition test and with double negation,
interactive configuration. I refer to this simply as constraint propaga- respectively. In Section 6, I comment on the status of the implemen-
tion in the sequel8 . tation. I conclude with some further observations in Section 7.
In this paper, I do not propose an own algorithm for constraint Finally, a disclaimer: While the motivation for this work lies in my
propagation with negative tables9 . Rather, I assume that a configura- past at SAP and is based on insights and experiences with the prod-
tor will already implement constraint propagation for positive tables, uct configurators there [3, 5], all work on this paper was performed
but it may not implement a corresponding algorithm (such as [9]) for privately during the last two years after transition into partial retire-
negative table constraints10 . ment. The implementation is neither endorsed by SAP nor does it
A tuple representing a disallowed combination of propositions reflect ongoing SAP development.
(p1 , . . . , pk ) in a negative variant table of arity k allows k obvious
inferences:
pj1 ∧ . . . ∧ pjk−1 → ¬pjk (1) 2 Framework
These could be applied at run-time if and where the configurator sup- My scope here is restricted to the problem of constraint propagation
ports it, e.g., where it is possible to remove a value from a domain in with negative tables. I construct a framework for this that is based on
a way that can be represented in the configurator11 . operations with sets. After an overview of the basic framework, I de-
In this paper, I characterize what can be achieved using pre- fine the relevant sets in Section 2.1, and present the actual framework
existing means of constraint propagation beyond (1) with negative I use for negative variant tables in Section 2.2.
tables that are maintained independently from the global domains A variant table T is characterized as follows: its arity expresses
for the mapped properties. I give a condition that can be tested during how many columns it has. The columns are indexed with j : 1 ≤
evaluation to determine if further restrictions via constraint propaga- j ≤ k, where k is the arity. Each column is mapped to a product
tion are possible (Section 4). The condition states that at least all but property, vj . I assume T to be in relational form, i.e., each table
one of the domains must be sufficiently restricted in order to achieve cell contains an atomic value (a string or number). Variant tables that
further filtering with the negative variant table. In a way, this general- allow intervals or wild cards in cells are not directly representable in
izes (1), which states that an inference is possible if all but one value relational form. Many of the results here could be extended to cover
assignments are known. this case, but I consider it out of scope here.
The condition test rests on the fact that the solution set of a nega- I view a variant table T in its role as a constraint only12 . In the
tive variant table with arity k can be easily decomposed at run-time language of constraints the product properties mapped to the columns
into k + 1 disjoint parts, of which k are in the form of Cartesian of the variant table are the constraint variables. I continue to refer
products (referred to as c-tuples in Section 2.2). This decomposition to them as product properties. The assumed relational form of the
is one of the results presented in this paper and applies independently variant table simplifies the correspondence between a table cell aij
and on top of the methods implemented in the configurator for arc (where i is the index of the row, and j is the index of the column) and
consistency. a value assignment vj = aij . Thus each row directly corresponds
A positive variant table can be transformed into a negative one by to a value assignment tuple (v1 = a1 , . . . , vk = ak ). In its role
negating (complementing) it. When processing this negative table the as a constraint, each row in T expresses a k-tuple of valid value
table is logically negated again, yielding an identical solution set, but assignments.
not an identical structure to the original table. I refer to this as double Each product property, vj , has a domain. The domain known at
negation, and discuss it as one possible approach to compression in maintenance-time for vj is called the global domain, Ωj , which
Section 5. Otherwise, compression of variant tables is a topic I deal may be unconstrained (infinite) if unknown (or otherwise infinite
with in [6]. as would be the case for a continuous interval). For negative vari-
I distinguish between information known to the modeler at the ant tables, I treat global domains as unconstrained, as discussed in
time the variant table is maintained (maintenance-time) from infor- Section 1. I refer to a domain known at run-time for vj as a run-time
mation known when configuring the product (run-time). Some cal- restriction, Rj , even if it also unconstrained or infinite.
culations can already be performed at maintenance-time, others best I assume that the configurator already implements constraint prop-
agation methods for arc consistency, e.g., implements some form of
8 I am only concerned with the propagation on each table constraint individ- a GAC algorithm [2, 8]. As a consequence, I do not delve into the
ually. The question of how to achieve overall arc consistency and how to details of any particular GAC algorithms here13 .
resolve inconsistencies is up to the methods pre-implemented in the con- The following example illustrates the concepts introduced so far,
figurator. The SAP VC, for example, does not backtrack, but performs con-
straint propagation via forward filtering albeit for a positive variant table. Examples for negative variant tables
9 The implementation is part of a prototype for exploring the compression are constructed in Section 3.
approach in [6]. This also handles negative variant tables, and thus an own
approach is implicit in that context 12 In the SAP VC configurator variant tables are also used in procedural
10 If it does implement such an algorithm, then the algorithm itself implicitly fashion, e.g., in “rules”
involves calculating the complement to the domains known at run-time 13 If the configurator also already implements some form of arc consistency
11 This will not be the case when the run-time domain is unconstrained, with negative table constraints such as [9], the basic approach will still
but then all methods of dealing with negative tables referred to cannot be apply. I shall indicate what differences must then be observed in the appro-
meaningfully applied priate places, below
Juha Tiihonen, Andreas Falkner, and Tomas Axling, Editors 82
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
Example 1 Table 1 is a positive variant table of t-shirt variants. In Example 1 it can be seen that it is possible to eliminate
Looking at this table, the global domains are {Small} and {M IB} after deciding on a red t-shirt. This is the ba-
sic inference of arc consistency, which I refer to as constraint propa-
• {Black, Blue, Red, W hite} for the product property “Color”, gation: filtering out values that are no-longer part of any valid tuple.
denoted by v1 Given a run-time restriction tuple R and a variant table T with
• {Large, M edium, Small} for the product property “Size”, de- solution set S T , then the set of remaining valid tuples is R ∩ S T .
noted by v2 T
I abbreviate the solution set S R∩S by S T ,R . If T is positive, then
• {M IB, ST W } for the product property “P rint”, denoted by v3 S T ,R
= T ∩ R. If T is negative, then S T ,R = R \ T .
If the customer wants a red t-shirt, but specifies nothing else, then Constraint propagation restricts the run-time restrictions Rj to
the run-time restrictions are πj (R ∩ S T ).
• R1 = {Red} for the product property “Color”
2.2 Negative Variant Tables
• R2 = {Large, M edium, Small} for the product property
“Size” For clarity, I denote a negative variant table by U. I take U to be
• R3 = {M IB, ST W } for the product property “P rint” in relational form and have arity k. The complement of U with re-
spect to π(U ) is a positive table constraint that can be calculated at
A GAC algorithm can then further restrict the domains of the prop- maintenance-time and depends only on U itself. I denote this com-
erty “Size” to {Large, M edium} and of the property “P rint” to plement by U
{ST W }. (There are only two rows in the table involving the color U = π(U ) \ U (6)
“Red”.)
Note that U = ∅ by construction if U has only a single line, be-
cause then π(U ) = U.
2.1 Definitions and Notation of Relevant Sets Given a run-time restriction tuple R, the solution set of U ∧ R
Let T denote a variant table of arity k for product properties is S U ,R = R \ U. This can be decomposed into two disjoint parts
v1 . . . vk . These are the product properties that are related via T as a (either of which may be empty, see Section 3 for examples):
constraint, and the only properties to consider when looking at T in
isolation, but their existence is not directly tied to T . Let Ω1 . . . Ωk S U ,R = (R \ π(U )) ∪· (U ∩ R) (7)
be known global domains of v1 . . . vk . I define the solution space, Ω, The first part (R \ π(U )) is just R with the c-tuple spanning all
as values that occur in U removed. The second part then re-adds all
Ω := Ω1 × . . . × Ωk (2) tuples in π(U) that occur both in U and R.
Any subset of the solutions space consisting of valid tuples defines The second part (U ∩ R) is just the solution set of U ∧ R. As U is
a constraint relation on v1 . . . vk . In particular, S T , the set of valid a positive variant table, this can be processed by the means available
tuples defined by T , is a subset of Ω. If T is in relational (extensive) to the configurator14 .
form, then S T = T for a positive table, and S T = Ω \ T for a The first part (R \ π(U )) can be decomposed into k disjoint c-
negative table. I refer to S T as the solution set of T . Generally, a tuples CjU ,R as follows (see Proposition 2):
solution set as defined above may not be finite. R
Let τ = (τ1 , . . . , τk ) ∈ Ω denote a tuple in the solution space. C1U ,R = π1 (U) × R2 × R3 × . . . × Rk
Given any X ⊆ Ω, I define the j-th column domain of X as R
C2U ,R = π1 (U) × π2 (U) × R3 × . . . × Rk
[ (8)
πj (X) := {τj } (3) ···
τ ∈X R
CkU ,R = π1 (U) × π2 (U) × π3 (U) × . . . × πk (U)
I call πj (X) the projection of X onto the j-th component, and define
or more explicitly for the omitted rows 2 < j < k:
the projection or constraint propagation operator π as:
R
π(X) := π1 (X) × . . . × πk (X) (4) CjU ,R = (π1 (U) × . . . × πj−1 (U)) × πj (U) × (Rj+1 × . . . × Rk )
The complement of a column domain πj (X) with respect to a Proposition 2 (R\π(U)) in (7) can be decomposed into the disjoint
run-time restriction Rj plays a central role in the decomposition in union15 (8) for an arbitrary ordering of the columns.
Section 2.2. Hence, I find it convenient to abbreviate its notation as:
Proof
R
πj (X) := Rj \ πj (X) (5) Each CjU ,R is a subset of R by construction.
R
The j-th component of CjU ,R is πj (U) . This is disjoint to πj (U).
For notational convenience I refer to any set C ⊆ Ω that is a
Cartesian product C = C1 × . . . × Ck as a c-tuple. All of the fol- So CjU ,R is disjoint to all CpU ,R ∀j < p ≤ k.
lowing are c-tuples No tuple x ∈ π(U) is in any CjU ,R , because x ∈ CjU ,R ⇒ xj ∈
R
• Ω itself πj (U) ⇒ xj ∈
/ πj (U) ⇒ x ∈
/ π(U).
• π(X) the tuple of column domains for in (4) 14 If the configurator implements an algorithm for negative GAC such as [9],
• the tuple of run-time restrictions, denoted by then U need not be explicitly calculated. Processing would not be affected
for this part
R = R1 × . . . × Rk 15 I exclusively use the term disjoint union to refer to a union of disjoint sets
[4]. I denote the disjoint union of two sets A and B by A ∪ · B, which
I refer to R as a whole as as a run-time restriction tuple implies that A ∩ B = ∅
83 Juha Tiihonen, Andreas Falkner, and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
For all other tuples y ∈ R, there is at least one component with 3.2 T-Shirt Example: MIB
/ πj (U). Let j ∗ denote the smallest such index. Then, it follows
yj ∈
by construction that y ∈ CjU∗,R , because ∀p < j ∗ : yp ∈ πp (U), The constraint M IB → Black in the t-shirt example could be for-
R
yj ∗ ∈ πj ∗ (U) , and ∀p > j ∗ : yp ∈ Rp . mulated as three exclusions against the original global domain of
the property Color yielding a negative variant table with three rows,
The decomposition (8) is meaningful, because if (R \ π(U)), the k = 2, v1 = P rint, and v2 = Color:
first part in (7), does not allow further constraint propagation, then
the GAC algorithm need not be applied for U ∩ R in the second part
M IB Red
at all. (All values in R are allowed by the first part.) I give a simple U = M IB W hite
criteria for when this is the case in Section 4. This is a necessary M IB Blue
precondition for a further reduction. Generally, it is easy to perform
constraint propagation on a constraint that is a c-tuple16 . Using the global domains given in Example 1, this means that
π1 (U) = {M IB} and π2 (U) = {Red, W hite, Blue}:
3 Examples
C1U ,R = {ST W } × {Black, Red, W hite, Blue}
I base my examples on the t-shirt model I introduced in Table 1. The (10)
global domains are listed in Example 1. In a real application setting, C2U ,R = {M IB} × {Black}
Table 1 would be used as the product model as is. For purposes of ex-
position here, I assume that the model evolves over time and further It still holds that U = ∅. So the solution set is still directly given
colors, sizes, and prints might be added in later model updates along by the first component in (7) and its decomposition in (8), and it
with associated constraints. The restriction to the initial 11 valid tu- follows from (10) that there are five tuples in the solution set. Again,
ples in Table 1 implements constraints to the effect that M IB implies constraint propagation does not produce a domain reduction.
Black and ST W implies ¬Small. If, instead, the domain restriction for v2 at run-time is R2 =
In this section, I use U to denote a negative variant table, and T to {Red, Blue} (but still R1 = Ω1 ), then
denote a positive one.
C1U ,R = {ST W } × {Red, Blue}
3.1 T-Shirt Example: STW C2U ,R = ∅ (= {M IB} × ({Red, Blue} \ π2 (U)))
The constraint ST W → ¬Small in the t-shirt example can be for-
mulated as a single exclusion, yielding a negative variant table U The solution set S U ,R is now two tuples (ST W, Red) and
with one row, k = 2, v1 = P rint, and v2 = Size (ST W, Blue). Constraint propagation produces a domain reduction
of R1 to {ST W }
U = ST W small
As noted, U = ∅.
Assume that the restricted domains at run-time are just the global 3.3 Original T-Shirt Example in a Single Negative
domains, i.e., R1 = Ω1 (property P rint) and R2 = Ω2 (Prop- Table U
erty Size). Then, the solution set S U ,R is directly given by the de-
composition (8) of the first term in (7)17 . This means that π1 (U) = In the sequel, the order of the complete set of constraint variables is
{ST W }, π2 (U) = {Small} and: v1 = Color, v2 = Size, v3 = P rint.
Let T be the variant table of the t-shirt in its original positive form
C1U ,R r = {M IB} × {Large, M edium, Small} given in Table 1. T has 11 solutions out of a possible 24. Thus com-
(9) plementing the table with respect to the global domains in Example
C2U ,R = {ST W } × {Large, M edium}
1 yields a negative table U with thirteen rows, k = 3, and
The solution set is the five tuples in (9):
(M IB, Large), (M IB, M edium), (M IB, Small), Black Small ST W
Red Small M IB
(ST W, Large), (ST W, M edium)
Red M edium
M IB
Constraint propagation does not produce a domain reduction (ver- Red Large M IB
ifiable by inspection). Red Small ST W
If, instead, the domain restriction for v2 at run-time is R2 = W hite Small M IB
{Small} (but still R1 = Ω1 ), then U =
W hite M edium M IB
W hite Large M IB
C1U ,R = {M IB} × {Small}
W hite Small ST W
C2U ,R = ∅ (= {ST W } × ({Small} \ {Small})) Blue
Small M IB
Blue M edium M IB
The solution set is now the tuple (M IB, Small). Constraint prop-
Blue Large M IB
agation produces a domain reduction of R1 to {M IB}. Blue Small ST W
16 Constraint propagation on a solution set in the form of a c-tuple means
intersecting the c-tuple with the given run-time restriction tuple R. In a Let R1 = Ω1 (Color), R2 = Ω2 (Size), and R3 = Ω3 (P rint).
product configuration context the values will most often be ordered. Hence, R
set operations can use binary search and are relatively efficient πj (U) = Rj for every j, therefore all πj (U) = ∅, and all CjU ,R =
17 The unaffected property Color could take any value. I take this up in Sec- ∅. In this case, T = U, and the tuples in Table 1 are just the solution
tion 3.5 set.
Juha Tiihonen, Andreas Falkner, and Tomas Axling, Editors 84
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
3.4 Extending the T-Shirt Model value Y ellow, and Ω2 (Size) and Ω3 (P rint) remain unchanged.
The following exclusions must be added to U in 3.3:
3.4.1 Extending the Global Domains
First, assume that after U in Section 3.3 has been maintained, the ¬(Y ellow, Small, M IB)
global domains of the properties are extended − without adding any ¬(Y ellow, M edium, M IB)
exclusions (U remains unchanged)18 − as follows: ¬(Y ellow, Large, M IB)
• Y ellow and DarkP urple are added to Ω1 (Color) ¬(Y ellow, Small, ST W )
Ω1 = {Black, Red, W hite, Blue, Y ellow, DarkP urple} In this situation
• XL and XXL are added to Ω2 (Size) π1 (U) = {Y ellow, Black, Red, W hite, Blue}
Ω2 = {Large, M edium, Small, XL, XXL} changes, and U changes accordingly. Two values are added to allow
the color of Y ellow in sizes Large and M edium with the print
• none is added to Ω3 (P rint) ST W . So |U| = 13. (11) holds with the modified version of π1 (U).
Again, both components in (7) contribute to the solution set S U ,R ,
Ω3 = {M IB, ST W, none} and after adding all remaining new values
Let the run-time domain restrictions reflect the changed global do-
C1U ,R = {DarkP urple} × R2 × R3
mains R1 = Ω1 , R2 = Ω2 , and R3 = Ω3 . Since U is not changed,
π(U ) does not change either. It still holds that C2U ,R = π1 (U) × {XXL, XL} × R3 (12)
C3U ,R = π1 (U) × π2 (U) × {none}
π1 (U) = {Black, Red, W hite, Blue}
π2 (U) = {Large, M edium, Small} As above, |R| = 6×5×3 = 90. Looking at (12), the total number
π3 (U) = {M IB, ST W } of solutions s for U is now
Hence, U is not changed either (still equal to Table 1), and with s = 15 + 30 + 15 + 13 = 73
R (The four new exclusions are subtracted from the solutions in Section
π1 (U) = {Y ellow, DarkP urple}
3.4.1)
R
π2 (U) = {XL, XXL}
R
π3 (U) = {none} 3.5 Excursion on Table Compression
(8) now yields From Sections 3.1 and 3.2 it is clear that the t-shirt table can be ex-
pressed in much more compact form by looking at the two constraints
C1U ,R = {Y ellow, DarkP urple} × R2 × R3 in two individual negative variant tables than at the single table in
C2U ,R = π1 (U) × {XXL, XL} × R3 (11) Section 3.3. In both Sections 3.1 and 3.2, the solution set is defined
only by the decomposition of (R \ π(U )) into c-tuples. An overall
C3U ,R = π1 (U) × π2 (U) × {none} solution set can be obtained by expanding these solution sets to ac-
In this example, both components R \ π(U) and U ∩ R in (7) are count for the respective unconstrained property, and then intersecting
non-empty and contribute to the solution set S U ,R . the resulting two expanded solution sets.
Note that |R| = 6 × 5 × 3 = 90, and (looking at (11)) the total Let the properties be ordered as v1 = Color, v2 = Size, and
number of solutions s for U is v3 = P rint, and the solution space Ω given by the global do-
mains in Example 1. In Section 3.1 the property v1 = Color is
R
s = |C1U ,R | + |C2U ,R | + |C3U ,R | + |U| = 30 + 24 + 12 + 11 = 77 unconstrained. Set π1 (U) = Ω1 (which implies π1 (U) = ∅ for all
R ⊂ Ω). Then, the decomposition of R \ π(U ) in (9) now results in
0
three c-tuples Cj(ST W ) (one of them empty by construction):
3.4.2 Extending the Constraints
0 R
If product management notices that Y ellow does not go with M IB, C1(ST W ) := ∅ (= π1 (U) × Ω2 × Ω3 )
then corresponding exclusions must be added to U. This can be done 0
(13)
C2(ST W ) := Ω1 × {Large, M edium} × Ω3
in several ways. In this example, I assume that Y ellow and the cor- 0
responding exclusions are added before any of the other changes to C3(ST W ) := Ω1 × {Small} × {M IB}
the domains are made19 . Then, the global domain given in Example 1
for the product property Color, denoted by Ω1 , is augmented by the Similarly, for Section 3.2 (10) can be replaced by:
0
C1(M IB) := {Black} × Ω2 × Ω3 )
18 Leaving U unchanged implicitly changes the underlying positive con-
straints. It now no-longer holds that M IB → black, This is taken to 0 R
be an intended consequence of using a negative variant table in a product C2(M IB) := ∅ (= {Black} × π2 (U) × Ω3 )
(14)
model 0
19 This assumption is made to keep the example simple. The general problem C3(M IB) := {Red, W hite, Blue} × Ω2 × {ST W }
of achieving a good compression directly from a positive table is addressed
in [6] The solution set S T of the original positive T given in Table 1 is
85 Juha Tiihonen, Andreas Falkner, and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
the intersection of the solution sets given by (13) and (14): 1. U = ∅. In this case, arc consistency is obtained solely by com-
puting the decomposition (8) of k c-tuples at run-time. Constraint
S T = C2(ST
0 0
W ) ∩ C1(M IB) ∪ propagation is achieved through directly intersecting these with
0 0
C2(ST W ) ∩ C3(M IB) ∪ R in a way that quickly tests the precondition of Lemma 3 and
0 0 Corollary 4.
C3(ST W ) ∩ C1(M IB) ∪
0 0 2. R \ π(U ) = ∅. In this case, the GAC algorithm implemented in
C3(ST W ) ∩ C3(M IB)
the configurator is applied to U (or a GAC-negative algorithm is
applied to U if this seems better).
= {Black} × {Large, M edium} × Ω3 ∪ 3. Both components (R \ π(U )) and U are non-empty. In this case,
{Red, W hite, Blue} × {Large, M edium} × {ST W } ∪ the component (R \ π(U )) is decomposed and processed as in the
first case, testing the pre-conditions in Lemma 3 and Corollary
{Black} × {Small} × {M IB} ∪ 4 at the same time. The constraint propagation methods of the
∅ (= {Red, W hite, Blue} × {Small} × ∅) configurator need to be applied to U, if this is still indicated after
processing the first part.
The 11 tuples of T are represented as 3 c-tuples. The complexity
of this compares favorably with the MDD representation in [1] for
the same example. The representation also compares favorably with 5 Double Negation of a Positive Variant Table T
the compression of the table to c-nodes introduced in [7] if a suit- In the sequel, I take T to be a positive table. I denote the negation of
able heuristic is applied. Thus, it should be possible to recover this T as the negative table ¬T := π(T ) \ T . Trimming any run-time
compact representation from the full table. This is a topic of [6]. restrictions to π(T ), ¬T (as a negative table) and T have the same
solution space, and constraint propagation on T can be replaced by
constraint propagation on ¬T . The approach seems advantageous,
4 Arc Consistency for Negative Variant Tables
if ¬T has a decomposition of the solution set (7) with a non-empty
Let a negative table U of arity k and a finite run-time restriction tu- first part (8), i.e., if ¬T is smaller than T . I refer to this approach as
R double negation.
ple R be given. (I assume in the sequel that πj (U) is finite for all
columns.) As an example, consider the extended model of the t-shirt as spec-
One approach at arc consistency with U is to use (7) directly at ified in Section 3.4.2. A representation as a positive table T has 73
run-time to discard any tuples in U from R constructing π(S U ,R ) at tuples (rows) as inidicated there. Negating T against the extended
the same time. The STR-Negative algorithm [9] is such an algorithm. global domains yields a table ¬T with 17 rows. ¬T is just the table
Here, I propose an alternative approach based on (7) and the de- U of Section 3.4.2 (and thus U there corresponds to ¬T here). Thus,
composition (8). As already noted, a further restriction of R is only as outlined there, ¬T has a decomposition as in (7). It has 13 rows
possible if the c-tuples in (8) allow a restriction. The lemma and its and the c-tuples indicated in (12).
corollary below provide a simple necessary condition for this. Double negation is not only an approach at compression for a table
with a small complement, but also allows applying Lemma 3 and
R Corollary 4 as a simple test, before actually evaluating the remaining
Lemma 3 If πp (U) 6= ∅ for some column with index p, then ∀j 6=
p : πj (R ∩ S U ) = Rj , i.e., no further reduction of any of the other doubly negated table ¬T . The process could be iterated, i.e., ¬T
domains is possible by constraint propagation using U. could be doubly negated in turn. A fixed point occurs if T = ¬T .
Proof Suppose that the premise of the lemma holds. Without loss of 6 Implementation/Work in Progress
generality, sort the columns such that p = 1. Then,
I have implemented the approach for treating negative tables I de-
R
C1U ,R = π1 (U) × R2 × R3 × . . . × Rk scribe here, including double negation, within a Java prototype ad-
dressing the greater context of compressing and compiling variant
R tables [6].
Any value in π1 (U) 6= ∅ supports all values in Rj for j ≥ 2.
As customers so far have not had the opportunity of maintaining
negative tables directly in product configuration models, I have no
This has a trivial but important consequence:
real data to evaluate this approach. Experiences are currently limited
R to testing for functional correctness. Besides testing with exemplary
Corollary 4 If πj (U) 6= ∅ for more than one column, then no re- tables such as variations of the t-shirt, I have applied the double nega-
duction of domains is possible by constraint propagation using U. tion approach to 238 SAP VC variant tables. These tables are also the
basis for the evaluation of the approach at compression in [6].
Lemma 3 and Corollary 4 generalize (1) to state that a reduction Complementing a sparse table is not feasible if the solution space
via constraint propagation is possible, if at least all but one of the is large. The implementation performs complementation on a repre-
domains are sufficiently restricted at run-time so that they lie within sentation I term a Variant Decision Diagram − VDD, and produces
R
the range of π(U), i.e., πj (U) = ∅. a result in a compressed form (see [6]). I have so far limited attempts
Recall that π(U) is determined when maintaining the variant table, at double negation to those of the 238 tables where the number of
whereas R is only known at run-time. tuples of the complement is smaller than the number of rows (tuples)
The examples in Section 3 illustrate that either both or only one in the original (relational) table. The result is given in Table 2. All
of the components in (7) need to be considered at run-time. Let a tables where this criterium does not apply are counted as Skipped.
negative table U of arity k and a run-time restriction tuple R be given. Of the remaining tables where double negation was attempted, those
Then, three cases can happen: where a reduction was realized (i.e., the VDD of T was larger than
Juha Tiihonen, Andreas Falkner, and Tomas Axling, Editors 86
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
that of ¬T ) are counted as Reduced. The total number of tables in this process ¬T is negated again (¬T ), which I refer to as double
the model and the number of those neither skipped nor reduced are negation. The purpose of double negation is that it may yield a ben-
given for completeness. eficial (partial) compression of the table, i.e., the table ¬T may be
I give more detailed results of tests with the implementation in smaller than T , with the remaining part of the solution set being a
[6]. As pointed out there, it is not yet clear whether double negation set of k c-tuples that additionally allows testing whether constraint
yields a gain over the general compression approach. propagation is possible at all for a given run-time restriction R.
Table 2. Tables amenable to double negation
ACKNOWLEDGEMENTS
I would like to thank all that took the time to comment on previous
Number of tables versions of this paper, and have thus contributed to its current form.
Total Skipped Reduced Not reduced This includes the anonymous reviewers, but also colleagues at SAP,
238 181 39 18 particularly Conrad Drescher and Andreas Krämer. I tired to incorpo-
rate all their suggestions. Any remaining flaws and dis-improvements
are solely my responsibility.
7 Conclusion REFERENCES
I presented an approach to handling configuration constraints defined [1] H.R. Andersen, T. Hadzic, and D. Pisinger, ‘Interactive cost configura-
by negative variant tables that can be integrated as an add-on to an tion over decision diagrams’, J. Artif. Intell. Res. (JAIR), 37, 99–139,
existing configurator, such as the SAP VC, with little risk. The origi- (2010).
nal mechanisms and architecture of the configurator are not touched. [2] C. Bessiere, ‘Constraint propagation’, in Handbook of Constraint Pro-
gramming, eds., F. Rossi, P. van Beek, and T. Walsh, chapter 3, Elsevier,
SAP customers specifically request that a constraint for a negative (2006).
table not be sensitive to subsequent changes to the global domains [3] U. Blumöhr, M. Münch, and M. Ukalovic, Variant Configuration with
of the affected product properties. This approach meets that require- SAP, second edition, SAP Press, Galileo Press, 2012.
ment. As the footnote to the example in Section 3.4.1 points out, [4] K. Ferland, Discrete Mathematics, Cengage Learning, 2008.
this may mean that some implicit positive constraints, valid before a [5] A. Haag, ‘Chapter 27 - product configuration in sap: A retrospective’,
in Knowledge-Based Configuration, eds., Alexander Felfernig, Lothar
change to the global domains, may no-longer be valid afterwards. Hotz, Claire Bagley, and Juha Tiihonen, 319 – 337, Morgan Kaufmann,
This emphasizes a modeling aspect of the problem: Is it feasible Boston, (2014).
and beneficial to offer the option of negative variant tables as part [6] A. Haag, ‘Column oriented compilation of variant tables’, in Proceed-
of the modeling environment in this fashion? This may be a tricky ings of the 17th International Configuration Workshop, Vienna, Austria,
September 10-11, 2015., pp. 89–96, (2015).
question. The implemented prototype offers a means for experiment- [7] G. Katsirelos and T. Walsh, ‘A compression algorithm for large arity
ing with the functionality, and thus a basis for discussing the merits extensional constraints’, in Principles and Practice of Constraint Pro-
and demerits of negative variant tables. gramming - CP 2007, 13th International Conference, CP 2007, Prov-
One main idea, implicit in the approach, is to make use of the idence, RI, USA, September 23-27, 2007, Proceedings, ed., Christian
distinction between information known at maintenance-time to the Bessiere, volume 4741 of Lecture Notes in Computer Science, pp. 379–
393. Springer, (2007).
modeler (the table content) and information known at run-time to the [8] C. Lecoutre, ‘STR2: optimized simple tabular reduction for table con-
configurator (the current domain restrictions). For a negative table U straints’, Constraints, 16(4), 341–371, (2011).
the finite column domains πj (U) can be determined at maintenance [9] Honbo Li, Yanchun Liang, Jinsong Guo, and Zhanshan Li, ‘Making sim-
time. For a given run-time restriction of the domains R the comple- ple tabular reductionworks on negative table constraints’, in Proceed-
R ings of the Twenty-Seventh AAAI Conference on Artificial Intelligence,
ments of the column domains to R (denoted by πj (U) ) must be July 14-18, 2013, Bellevue, Washington, USA., eds., Marie desJardins
calculated at run-time. This calculation is efficient, as the required and Michael L. Littman. AAAI Press, (2013).
set-operations can make use of the natural order imposed on the do-
main values by the business context.
R
If more than one πj (U) is non-empty at run-time, constraint
propagation does not yield a further restriction of the run-time do-
R
mains. If one πj (U) is non-empty, then only the run-time restric-
tion for that column can be further restricted. When a restriction is
possible by constraint propagation, the GAC algorithm only needs
to be applied to the positive table U, the complement of U to π(U).
The remaining part of the solution set of U is the set-difference be-
tween two c-tuples (Cartesian products). I showed in Proposition 2
that such a set-difference can be decomposed into k disjoint c-tuples,
where k is the arity of U. Constraint propagation on c-tuples is again
based on set operations that are assumed to be efficient, given the
value ordering on the domains.
Of course, the approach also applies to the general case that neg-
ative tables are merely meant as a short-cut to maintaining an other-
wise lengthy positive variant table.
The approach can also be applied to a positive variant table T by
negating it, and treating its complement ¬T as a negative table. In
87 Juha Tiihonen, Andreas Falkner, and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria