Supporting Open Domains in Collaborative Modular Modeling Albert Haag1 Abstract. In commercial practice, modeling configurable products cerning electrical features require different expertise than those con- is often collaborative and modular. The former refers to the fact that cerning hydraulics. different teams in a company may work autonomously when con- Extensional lists of feature combinations are important modeling tributing to a product model. The latter refers to the fact that some elements that define variability in a very direct and intelligible man- elements of a model may be intended for re-use in multiple prod- ner. We refer to them as variant tables following the terminology uct models. When maintaining such model fragments, the actual do- of the SAP Variant Configurator (SAP VC) [2]4 . Variant table con- mains of the product properties, which are to be effectively applied in tent may be updated frequently by product data engineers, decoupled later configuration, may be only partially known to the modeler. For from other changes to the model. These engineers have criteria for in- example, using a wildcard in a variant table (a list of valid com- cluding or excluding feature combinations, but they do not need to binations of product features) to express “anything goes” implies know the complete product models. that an exact knowledge of the underlying domains is not impor- This is a short paper based on observations about modeling in tant to the modeler. The same is true for negative variant tables that practice. The motivation and insights for needing to deal with open list exclusions. Domains are explicitly declared as open, when non- domains, which I look at here, come from discussions in the Con- standard extensions of product features are foreseen – “additional figuration Workgroup (CWG) [3], an SAP centric user group, over values are allowed”. This is meant to allow a sales-engineer to pro- the years. The paper discusses three cases where open domains5 may vide non-modeled features in an impromptu manner. In this short need to be considered: paper we propose a way to deal with open domains in configuration and present some results for maintaining arc-consistency with open • Negative variant tables listing excluded feature combinations domains. These results build on and extend insights from previous • Wildcards (placeholders for allowing any feature) work [6, 13]. • Non-modeled, impromptu product features6 This paper is organized as follows: Section 2 contains some back- 1 Introduction ground and notation. Section 3 is a reprise of the results in [6] con- cerning negative variant tables. Section 4 discusses the engineer- Most current modeling of configurable products is based on the to-order requirement of allowing non-modeled features and feature closed-world assumption that all problem variables and their do- combinations, introducing a symbol ’&other’ to refer to the poten- mains are part of the model. This assumption is at the very heart of tially infinite set of non-modeled features of a product property. We the definition of a constraint satisfaction problem (CSP), which pos- refer to such a symbol as a quasi-finite symbol (qf-symbol), as pro- tulates a finite set of variables, each with a finite domain [5]2 . How- posed in [13]. Section 5 formalizes the use of wildcards. Section 6 ever, there are practical situations, when the closed-world assumption deals with the handling of the qf-symbol ’&other’ in an interactive does not hold. One example is an engineer-to-order scenario, where a configuration. Finally, Section 7 gives conclusions and an outlook. sales-engineer is allowed to supply unforeseen product features3 ex- tempore during a sales configuration. The closed-world assumption 2 Background and Notation is also limiting in modular modeling. The responsibility for model- ing may be distributed among different teams, each working inde- This is a short paper and a review of literature will be brief. The au- pendently to produce a re-usable part of a model. Where products thor’s insight into product configuration in practice stems from long or solutions contain multiple components, each component might be personal involvement in the topic working for SAP and from dis- modeled independently. Also, product features may be maintained cussions in the CWG [3]. Documentation of commercial configura- centrally company-wide, not product by product. Central product tion practice is still hard to come by. There exists a standard mono- features are typically subject to continual updates. Finally, modeling graph about classic SAP Variant Configuration, now available in a may be distributed subject to technical expertise. Constraints con- second edition [2]. Furthermore, some chapters in [4] are devoted to commercial configurators, but the information there is far from 1 PMH - Product Management Haag GmbH, Germany, email: albert@product-management-haag.de 4 In SAP configurators, product properties are referred to as characteristics 2 It is possible to relax the requirement of finiteness [13]. For example, the and product features either referred to as features or as characteristic value use of real (floating point) numbers and intervals is common. assignments. 3 A product feature refers to a value assignment to a product property. In 5 When the exact domain of a product property is not known to the modeler, some industries, a single symbol (e.g. 0 RED0 ) has a company-wide inter- it is considered to be open. pretation (e.g. as Color = ’Red’). Here, Color is a product property, which 6 Product properties may either have no features defined, or only have “stan- corresponds to a CSP variable. dard” features defined, but allow additional features at run-time. Copyright 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0) being technically complete. Also, there have been various contribu- 3 Reprise: Negative Variant Tables tions to this workshop series, two arbitrary examples being [18, 19]. In contrast, we consider both constraint programming [17] and its use Let U be a negative variant table (listing excluded feature combina- in product configuration [4, 14] to be mature and well documented. tions). Any combination not excluded by U is implicitly allowed by The notation and results about arc-consistency with negative variant U. Therefore, it is natural to consider what is valid with respect to tables in Section 3 are adapted from [6]. U at runtime (when actually configuring) and not when maintaining We assume that all valid configurations of a product can be de- the table (modeling time). Previous work [6] deals with maintaining scribed at runtime using a finite set of k product properties7 , each arc consistency [1, 16] in this situation. The main observation there property pj : 1 ≤ j ≤ k with a domain Rj , perhaps supplied dy- is that if a feature, which does not occur anywhere in the table, is namically at runtime. Thus, the space of all valid and invalid config- choosable at runtime, then all choosable features of all other proper- urations can be represented as the Cartesian product: ties remain choosable. An example: assume a T-shirt comes in vari- ous sizes and can sport an imprint. Suppose only one combination of R := R1 × R2 × . . . × Rk (1) imprint and size is known to be excluded: an imprint named ’STW’ is not available in size ’S’.9 Table 1 shows the corresponding nega- R can be seen as a k-dimensional space. Each point r ∈ R tive variant table. Any imprint except ’STW’ is available in all sizes. Any size except ’S’ is available in all imprints. Figure 1 illustrates a r = (f1 , f2 , . . . , fk ) ∈ R (2) disjoint decomposition (7) of the solution set R (1) for the negative variant table in Table 1. represents either a valid or an invalid configuration, where fj is a feature pertaining to property pj . We call any point in R an r-tuple, Table 1. U1 : Excluded Imprints / Sizes and any Cartesian product of product property subdomains a c-tuple. We can envision a c-tuple as a k-dimensional cuboid in R Size Imprint S STW (C1 × C2 × . . . × Ck ) ⊂ R (3) The r-tuple in (2) can be considered as a special case of a c-tuple in (3), if we treat the individual features as singleton sets: 'S' × {f1 } × {f2 } × . . . × {fk } C-tuple-2: Treating the configurations listed in a given variant table T as a set of points in the k-dimensional solution space R, we define D in (4) to be the c-tuple for the cuboid circumscribing T .8 We give an example C-tuple 1: of these sets in Section 3. × D := D1 × D2 × . . . × Dk (4) For notational simplicity we additionally define Qj to refer to the complement of Dj with respect to Rj . Q is the corresponding c- Excluded tuple of all Qj : 'S' × 'STW' Figure 1. Runtime solution set consisting of two c-tuples Qj := Rj \ Dj (5) Q := Q1 × Q2 × . . . × Qk (6) We observe that the solution space R in (1) can be represented Assume that Color is also a property of the T-Shirts and that a as the disjoint union of D and the k c-tuples Cj in (7). Figure 1 particular imprint ’MIB’ is not available in the colors ’Blue’, ’Red, illustrates a simple case of this decomposition. and ’White’. Then both exclusions can be collectively expressed in a negative variant table as in Table 2: C1 = Q1 × R2 × R3 × . . . × Rk C2 = D1 × Q2 × R3 × . . . × Rk (7) Table 2. U2 : T-Shirt Excluded Feature Combinations ··· Ck = D1 × D2 × D3 × . . . × Qk Imprint Size Color MIB S;M;L;XL Blue;Red;White We remark that a variant table has a (non-unique) representation STW S Black;Blue;Red;White as a disjoint union of c-tuples (cf. [7, 15] and the examples in Section 3). To make the example more complete, we assume a further T-Shirt 7 If the product consists of only one component, its properties can readily property Fabric which is not relevant for formulating exclusions. We be identified by name. If the product consists of multiple components with configurable properties, then a property must additionally be identified by order the properties as vp1 = Imprint, vp2 = Size, vp3 = Color, a reference to the component. and vp4 = F abric. We assume runtime domains R as in (8) (the 8 We consider T to be fixed and omit references to it to keep the notation simple. 9 T-shirt examples with this restriction are elaborated more fully in [6, 13] 2 c-tuple D circumscribing U (Table 2) is also given in (8)): “standard” features to be offered are modeled, but additional non- modeled features are allowed. Following an approach in previous R1 = {MIB,STW,EnvHero} D1 = {MIB,STW} work [13], we introduce a quasi-finite symbol (qf-symbol) 0 &otherj0 R2 = {S,M,L,XL} D2 = {S} to represent the non-modeled features of property pj , which can be (8) R3 = {Black,Blue,Red,White} D3 = {Blue,White,Red} infinite, finite, or empty. The symbols 0 &otherj0 cannot be explicitly referred to in a variant table. R4 = {Cotton,Mixed,Synthetic} D4 = ∅ A variant table allows partitioning Rj , the runtime domain of a Then the decomposition (7) looks as follows: property pj , into Dj and Qj as in (5). Dj collects all features refer- enced in the variant table for pj and thus does not contain the symbol C1 = EnvHero × R2 × R3 × R4 0 &otherj0 . Where a runtime domain allows non-modeled features, C2 = MIB, STW × M, L, XL × R3 × R4 i.e. 0 &otherj0 ∈ Rj , then 0 &otherj0 is part of Qj , not in D. For a (9) negative variant table, the results of Lemma 1 and Corollary 2 apply C3 = MIB, STW × M, L, XL × Black × R4 directly, and 0 &otherj0 will not be removed from consideration via C4 = MIB, STW × M, L, XL × Black × R4 \ D4 arc-consistency due to the table. The set of valid T-Shirt configurations T within D is In contrast, a positive table is a constraint and will restrict domains to lie within D as defined in (4), removing all symbols 0 &otherj0 T = (D \ U) (10) from R. However, a positive table can also be seen to exclude any combination from D not in the table. Formally, we could reverse the and the overall set of valid configurations T∗ within R is roles of T and U in (10), using the positive table to define a negative T∗ = C1 ∪ C2 ∪ . . . ∪ Ck ∪ T (11) table (its complement). This would make sense if there were a way to allow “additional combinations”, which suggests itself for reasons Let πj (R) ⊂ R (12) be the reduction on R that that can be of symmetry, but is not a modeling requirement the author has so achieved by enforcing arc-consistency using U far encountered in practice. Nevertheless, if we were to allow such an interpretation of a positive variant table “pour le moment”, the π(R) := π(R)1 × π(R)2 × . . . × π(R)k (12) results of Lemma (1) and Corollary (2) apply, and 0 &otherj0 will not The following is a reformulation of the major results from [6]. We be removed from consideration via arc-consistency due to the table. take R to be decomposed as in (7). Lemma 1 If Qp 6= ∅ for some p, then ∀j 6= p : π(R)j = Rj , 5 Wildcards and C-Tuples i.e., no further reduction of any of the other domains is possible via Variant tables can be represented in a significantly more compact arc-consistency with U. form when using rows of c-tuples [7, 8, 15]. The practical relevance of a c-tuple representation is the topic of previous work [10, 11]. Ta- Proof Without loss of generality, sort the columns such that p = 1. ble 3 is a positive formulation of Table 2 in three c-tuples. It takes the If Q1 6= ∅ then C1 = Q1 × R2 × R3 × . . . × Rk 6= ∅ and any feature properties and their domains Rj to be defined as in (8). C-tuples can in Q1 supports all features in Rj for j ≥ 2. be represented naturally in a spreadsheet as rows with multi-valued This has a trivial but important consequence (also taken from [6]): cells, but most relational databases do not have straightforward sup- port for a c-tuple representation. Corollary 2 If more than one non-empty Qj exists, then no domain reduction at all is possible via arc-consistency with U: Table 3. T1 : Valid T-Shirt Variants ∃Qj1 , Qj2 : j1 6= j2 ∧ Qj1 , Qj2 6= ∅ =⇒ π(R) = R Imprint Size Color To summarize: Given a negative variant table U, runtime domains MIB S;M;L;XL Black R, and the space D, spanned by the table U (as in (4)). If more than STW M;L;XL Black;Blue;Red;White one set Qj = Rj \ Dj is non-empty at runtime, then a general arc EnvHero S;M;L;XL Black;Blue;Red;White consistency (GAC) algorithm [1] does not need to be applied – no reduction would be obtained. Otherwise, a GAC algorithm should be applied on the potentially smaller solution space D, yielding π(D). The use of a wildcard symbol is common in variant tables. Here, If exactly one set Qp is non-empty, then the only reduction achieved we treat a wildcard symbol in a c-tuple as a reference to the runtime is π(R)p = Qp ∪ π(D)p . All features in Qp remain choosable and domains, which may contain both modeled and non-modeled fea- for j 6= p all features in Rj remain choosable. If there is no non- tures. We denote the wildcard symbol for property pj by Ωj .11 Table empty set Qj , then π(R) = π(D), i.e. the reduction obtained by the 4 is a representation of Table 3 using wildcards. GAC on D holds. Table 4. T2 : Valid T-Shirt Variants with Wildcards 4 Allowing Additional Non-Modeled Features Imprint Size Color Some property domains may be left completely undefined explicitly. MIB Ω2 Black This delegates the definition of the domains to other means, such STW M;L;XL Ω3 as variant tables. We treat features referenced in a variant table (not EnvHero Ω2 Ω3 counting wildcard symbols)10 to be modeled also. Sometimes, the 10 In this section, we assume that a variant table does not contain wildcards. 11 The wildcard symbol used in practice varies, “∗” is common. In the classic Wildcards are dealt with in Section 5. SAP VC an empty cell in a variant table is treated as a wildcard. 3 Table 4 lists the valid T-Shirt variants making use of wildcards. REFERENCES Regarding the wildcards, we assume that the modeled features are [1] C. Bessiere, ‘Constraint propagation’, In Rossi et al. [17], chapter 3. the Rj in (8).12 Furthermore, the properties Imprint and Color al- [2] U. Blumöhr, M. Münch, and M. Ukalovic, ‘Variant tables in detail’, low (additional) non-modeled features. The runtime domains R are in Variant Configuration with SAP, second edition, SAP Press, chapter depicted in (13).13 2.6.3, 152–158, Galileo Press, (2012). [3] CWG. SAP Configuration Workgroup. https://www. configuration-workgroup.com, 2021. Accessed: 2021-06- 04. R1 = {MIB,STW,EnvHero} ∪ &other1 [4] Knowledge-Based Configuration, eds., Alexander Felfernig, Lothar R2 = {S,M,L,XL} (13) Hotz, Claire Bagley, and Juha Tiihonen, Morgan Kaufmann, Boston, 2014. R3 = {Black,Blue,Red,White} ∪ &other3 [5] Eugene C. Freuder and Alan K. Mackworth, ‘Constraint satisfaction: An emerging paradigm’, in Handbook of Constraint Programming, From the perspective of a GAC algorithm, the qf-symbols eds., Francesca Rossi, Peter van Beek, and Toby Walsh, volume 2 of 0 &otherj0 are just like any other symbol. A GAC algorithm can be Foundations of Artificial Intelligence, 13–27, Elsevier, (2006). applied in the usual way. The GAC algorithm may remove Ωj as a [6] Albert Haag, ‘Arc consistency with negative variant tables’, in Proceed- ings of the 17th International Configuration Workshop, Vienna, Austria, whole, but it will not individually remove any features that are part September 10-11, 2015., eds., Juha Tiihonen, Andreas A. Falkner, and of Ωj at runtime. Tomas Axling, volume 1453 of CEUR Workshop Proceedings, pp. 81– 87. CEUR-WS.org, (2015). [7] Albert Haag, ‘Managing variants of a personalized product’, Journal of 6 Proposed Handling of Open Domains in Intelligent Information Systems, 1–28, (2016). [8] Albert Haag, ‘Assessing the complexity expressed in a variant table’, Configuration in Proceedings of the 19th International Configuration Workshop, La Defense, France, September 14-15, 2017., pp. 20–27, (2017). Just as a GAC algorithm would treat the qf-symbols 0 &otherj0 like [9] Albert Haag, ‘Quasi-finite domains: Dealing with the infinite in mass any other value, so would this symbol be presented to an agent per- customization’, in 20th Configuration Workshop (ConfWS 2018), eds., forming a configuration task. It should be possible for this agent to Alexander Felfernig, Juha Tiihonen, Lothar Hotz, and Martin Stet- tinger, number 2220 in CEUR Workshop Proceedings, pp. 77–84, Aachen, (2018). • to exclude non-modeled values by deselecting 0 &other0 [10] Albert Haag. Making more of variant tables in standard VC. Presenta- • to exclude all modeled values by selecting 0 &other0 tion at the CWG Virtual Spring Conference, Hamburg, Germany, May • to specify a set of non-modeled values to use for 0 &other0 26-June 19, 2020., 5 2020. [11] Albert Haag, ‘Toward data-driven modeling of configurable products’, in Proceedings of the 22th International Configuration Workshop, Vin- cenza, Italy, September 10-11, 2020., pp. 76–80, (2020). 7 Conclusion and Future Work [12] Albert Haag and Laura Haag, ‘Empowering the use of variant tables in mass customization’, in Proceedings of the MCP-CE 2018 conference, This paper takes a look at some modeling techniques that are long Novi Sad, Serbia, September 19-21, 2018., pp. 180–189, (2018). established in practice but where a clear specification seems miss- [13] Albert Haag and Laura Haag, ‘Further empowering variant tables for ing. The observations made here and in previous work [9, 11, 12, 13] mass customization’, International Journal of Industrial Engineering and Management (IJIEM), 10(2), (2019). are based on the author’s personal experiences with the SAP config- [14] Ulrich Junker, ‘Configuration’, in Handbook of Constraint Program- urators, as well as on general input from the product configuration ming, eds., Francesca Rossi, Peter van Beek, and Toby Walsh, volume 2 community. The topics dealt with here are the use of negative vari- of Foundations of Artificial Intelligence, 837–873, Elsevier, (2006). ant tables, the use of wildcards in variant tables, and dealing with [15] G. Katsirelos and T. Walsh, ‘A compression algorithm for large arity product property domains that allow the additional product features extensional constraints’, in Principles and Practice of Constraint Pro- gramming - CP 2007, 13th International Conference, CP 2007, Prov- to be added to their domain at runtime in an impromptu manner. All idence, RI, USA, September 23-27, 2007, Proceedings, ed., Christian have in common that they allow the domains at runtime to differ from Bessiere, volume 4741 of Lecture Notes in Computer Science, pp. 379– what was known at modeling time (open domains). 393. Springer, (2007). The approach to arc-consistency with negative tables in Section 3, [16] C. Lecoutre, ‘STR2: optimized simple tabular reduction for table con- straints’, Constraints, 16(4), 341–371, (2011). first introduced in [6], has been implemented in a prototype. Work [17] Handbook of Constraint Programming, eds., F. Rossi, P. van Beek, and is underway to verify this in a commercial setting. The handling of T. Walsh, Elsevier, 2006. non-modeled features using a qf-symbol 0 &other0 discussed in Sec- [18] Carsten Sinz, Albert Haag, Nina Narodytska, Toby Walsh, Esther M. tion 4 has not yet been implemented. This is imminent future work. Gelle, Mihaela Sabin, Ulrich Junker, Barry O’Sullivan, Rick Rabiser, Wildcards have been in practical use for decades. The main contribu- Deepak Dhungana, Paul Grünbacher, Klaus Lehner, Christian Feder- spiel, and Daniel Naus, ‘Configuration’, IEEE Intell. Syst., 22(1), 78– tion of Section 5 is to clarify that wildcards are meant to refer to the 90, (2007). runtime domains and how they coexist with non-modeled features. [19] Juha Tiihonen, Ville-Valtteri Korppila, Jorma Heimonen, and Andreas The proposals of how to deal with non-modeled features in Sections Anderson, ‘Structure oriented sales configuration of precast concrete 5 and 6 are new. Particularly, how and to what extent arc consistency production factories’, in Proceedings of the 22th International Config- uration Workshop, Vincenza, Italy, September 10-11, 2020., pp. 1–8, can be established with open domains as discussed here, is seen as a (2020). contribution to practical configuration. 12 These domains were introduced as runtime domains in (8), but are assumed to be the modeled domains here. 13 Columns consisting only of wildcards can be added to or removed from a variant table at will, without affecting the meaning or processing of the table. For example, a column for the fourth T-Shirt property Fabric with a wildcard Ω4 in all three rows can be arbitrarily added to Table 4 if oppor- tune. 4