Speeding up Derivative Configuration from Product Platforms

1. Introduction

To increase variety, improve customer satisfaction, reduce lead-times, and shorten costs, many companies have shifted from mass production to mass customization [1]. This shift of paradigm enriches the mass production economies of scale with custom manufacturing flexibility by developing families of related products instead of single products. From this perspective, designing a product family is the process of capturing and modeling multiple product variants to satisfy different market niches. A generic architecture, named product platform, is designed to support the creation of customized products called derivatives.

Product platforms usually support a high quantity of derivatives. For instance, the number of derivatives for product platforms in the automotive industry may range from 10³ for the smallest Peugeot and Nissan car models, to 10¹⁶ or 10²¹ for the BMW 3-Series and Mercedes C-Class, respectively [2]. To achieve that flexibility, a number of configuration options are available. For example, the Peugeot 206 and Mercedes C-Class car models have 86 and 389 customer selectable options, respectively. Typically, not all option combinations are valid. There may be option incompatibilities (e.g.,“manual transmissions are not compatible with V8 engines”), option dependencies (e.g., “sport cars require manual gearbox”), etc. Configuring a valid derivative implies ensuring that all constraints between its constituent components are satisfied. Checking by hand those constraints is infeasible for all, but the most trivial product platforms, so derivative configuration is usually assisted by automated configurators [3]. Some examples of commercial configurators are Configit [4], SAP Product Configurator [5], Oracle Configurator [6], etc. In addition, many automotive companies have their own configurators. For instance, Volvo uses KOLA, Scania uses SPECTRA, Mercedes uses SMARAGD, etc.

Our work enriches existing configurators by reducing the number of steps required to configure a valid derivative. It takes advantage of the fact that, due to the component composition constraints, some decisions may be automatically derived from other decisions previously made. Therefore, the order in which decisions are made has a strong influence on the number of decisions required to complete a derivative. For instance, given the constraint “sport cars require manual gearbox”, a customer might configure a sport car using two decision orderings: one requiring two steps (i.e., Step 1, select “manual gearbox”, and Step 2, select “sport car”) or another one using just a single step (i.e., select “sport car”, so that the decision to select “manual gearbox” is implicitly made).

As van Nimwegen et al. [7] note, customers sometimes prefer to first answer questions that are important to them, or easy to answer, before being led through the remaining questions [7]. In this sense, our approach respects customer preferences. Instead of imposing a fixed ordering, it suggests orderings dynamically, reacting to the customer decisions. In particular, the process to get a derivative is performed in successive steps. In each step, the customer gets a question ranking, selects one of the questions and answers it. In the next step, the question ranking is readjusted to account for the customer’s answer. The computation of the ranking is grounded on the information theory concept of entropy, which was introduced by Shannon [8] and measures the average uncertainty of a random variable.

At the first configuration step, the uncertainty is total. With no information at all, the configurator cannot figure out which derivative the customer desires. As the process advances, configuration options are eliminated according to the customer decisions, and so, the information about the final configuration increases (i.e., the set of included/excluded components grows). Consequently, the entropy decreases. When the derivative is totally configured, there is no uncertainty, and the entropy is zero.

As we will see, not only our approach, but also Mazo et al.’s Heuristic 3 [9] and Chen et al.’s approach [10] require computing the probabilities of all variables in a Boolean formula. The usual way to perform such task is calling repeatedly a logic engine, e.g., a SATsolver or a binary decision diagram (BDD) library, one time for each variable [11]. Unfortunately, this approach has a high computational cost and, thus, imposes long response times, hindering customer-configurator interactivity. To overcome such a problem, this paper proposes an algorithm that computes efficiently variable probabilities using BDDs. Since more complex logics than the propositional one, which include integer arithmetic, transitive closure, etc., can be reduced to Boolean functions [12,13] and, thus, encoded as BDDs, our algorithm is general enough to support most configuration model notations.

The validity of our approach has been tested on two benchmarks widely used by the configuration and software product line communities: the Renault Megane platform provided by the car manufacturing company Renault DVI [14] and the Electronic Shopping case study [17]. Results show that our approach requires less configuration steps than related work, and that our BDD algorithm gets short response times, supporting this way not only our approach but also other methods proposed in related work.

The remainder of this paper is structured as follows. Section 2 presents the running example that we will use to motivate and illustrate our work. Section 3 summarizes related work to our approach. Section 4 introduces the concept of entropy and describes how to compute it from a configuration model. Later, our entropy-driven approach is described in detail. Section 5 reports the experimental validation of our approach. Finally, Section 6 outlines the conclusions of our work.

2. Motivational Example

This section illustrates the problem our approach tackles using an example provided by [18], where derivatives are cars with different automated driving capabilities.

To model the configurable options of a product family, a number of different notations are available. For instance, feature diagrams (FDs) [19], decision diagrams [20], the Configit language, the SAP Product Configurator language, the Oracle Configurator language, etc. Interestingly, most of those notations are semantically equivalent [21,22]. In fact, automated configurators instead of processing configuration models directly usually translate them into a propositional logic representation, such as a logic formula in conjunctive normal form, a BDD, etc. That logic representation is then processed using off-the-shelf tools, such as SAT solvers, BDD engines, etc. (see Section 4.1.2. for an explanation of the configuration model to logic translation). The input to our approach is the logic representation of the configuration model, so it is independent of the original notation used to specify the model.

To show what a configuration model looks like, please refer to Figure 1, which models our running example as an FD (a hierarchically arranged set of features with different relations among them). This paper follows the generic semantics for FDs given by Schobbens et al. [22]. Figure 1 includes three kinds of hierarchical relations:

• optional, denoted by simple edges ending with an empty circle; e.g., cars may (or may not) include an automated driving controller (ADC).

• mandatory, denoted by simple edges ending with a filled circle; e.g., if a car has an ADC, it must include some kind of collision avoidance braking (CAB).

• alternative, denoted by edges connected by an arc; e.g., standard avoidance (SA) and enhanced avoidance (EA) are the mutually exclusive options for collision avoidance braking (CAB).

To manage the complexity of modeling the similarities and differences among the derivatives of a product family, the FD notation follows a divide and conquer strategy. Derivative variabilities are modeled by progressively decomposing complicated and abstract features into simpler ones, until elemental features, which are directly implemented by physical components, are reached. The hierarchical structure of an FD graphically depicts such conceptual decomposition. From here on, derivatives will be expressed enumerating the final components they include, i.e., using references to the terminal nodes of the FD. For example, {PP, LRF, FRF, ¬SA, EA} expresses the configuration of a car with components PP, LRF, FRF, EA and without SA.

The FD notation supports narrowing the configuration space by adding additional cross-tree constraints. For instance, Figure 1 represents as $“\text{PP}\stackrel{\text{requires}}{\to }\text{LRF}”$ the fact that cars with parallel parking need to include the lateral range finder component. Thus, a car derivative with components {PP, ¬LRF, ¬FRF, SA, ¬EA} complies with the FD relations, but is not valid because it violates the constraint $“\text{PP}\stackrel{\text{requires}}{\to }\text{LRF}”$.

For a configuration model with n options and no component interdependencies, the number of possible configurations is 2ⁿ. Due to the feature relations and additional cross-tree constraints, the number of valid configurations in the example is reduced from 2⁵ = 32 to the 13 ones summarized in Table 1.

To configure a car, the decision-maker needs to answer a sequence of questions. For example, the sequence (1) is EA in the configuration? no, (2) FRF? no, (3) LRF? yes, (4) PP? yes configures Car 11 in Table 1. Current automated configurators guarantee the derivation of valid products ensuring the satisfaction of all model constraints. When the first question is answered, the configurator deduces that the car being configured necessarily includes SA (otherwise, the alternative relation between EA and SA would not hold). This way, the configurator is indirectly saving the decision-maker from answering the irrelevant question, “is SA in the configuration?”

The goal of our work is to make the most of the configuration model constraints going beyond current configurators to minimize the number of questions required to specify a derivative. To do so, our approach tries to find an optimal question ordering that maximizes the number of decisions automatically derived from other questions previously answered.

A straightforward approach to get such optimal question ordering is computing for each valid product all possible orderings and, thus, finding the ordering with less questions on average for every product. Table 2 sums up the needed computations. For instance, the next-to-last column summarizes the number of questions needed for derivative {PP, LRF, FRF, SA, ¬EA}. Ordering PP ≺ LRF ≺ FRF ≺ SA ≺ EA needs three questions, LRF ≺ PP ≺ FRF ≺ SA ≺ EA needs four, and so on. Afterwards, the average number of questions for each ordering is computed. Using this approach in the previous example, ordering PP ≺ LRF ≺ FRF ≺ SA ≺ EA would be selected as an optimal one. As a result, the question sequence for Derivative 11 in Table 1 would be shortened to (1) is PP in the configuration? yes, (2) FRF? no, (3) SA? yes, removing the need for answering “if LRF is in the configuration”.

Unfortunately, this approach requires m · n! computations, where n is the number of components of the configuration model and m is a number ≤ 2ⁿ. Therefore, it is extremely expensive in computational terms and does not scale, except for the most trivial configuration models. To overcome the scalability limitations of the former approach, this paper proposes a heuristic solution grounded on the information theory concept of entropy.

3. Related Work

Research on automated configurators is mainly focused on consistency checking and optimization [3,23]. For example, reasoning engines, such as BDD libraries, SAT solvers and logic-truth maintenance systems, have been used to detect invalid derivatives (i.e., those which violate some option dependency or incompatibility) [24–26], to provide explanations for configuration flaws [27,28], to optimize configurations (i.e., to find configurations whose cost is less or equal than a given one) [29–31], etc.

Despite the importance of the interactive question ordering problem that our work tackles, which was pointed out by Steinberg more than thirty years ago [32], there is little research on it. A recent approach that specifically deals with this problem is provided by Chen et al. [10], who propose to minimize the number of configuration steps by sorting the components according to their probability of being included in a derivative. Such a probability is computed by Equation (1).

In their original paper and with a fully equivalent meaning, Chen et al. [10] use the term selectivity instead of probability. As our approach follows an entropy driven heuristic and the information theory concept of entropy is defined in terms of probability (see Section 4.1.1.), we have preferred to use probability throughout this paper.

In addition to Chen et al.’s approach, Mazo et al. [9] proposes the following heuristics for ordering configuration questions:

• Heuristic 1: Components with the smallest domain first. Choose first the component with the smallest domain. The domain of a component is the set of possible values that the component can take according to its domain definition and the constraints in which the component is involved.

• Heuristic 2: The most constrained components first. Choose the component that participates in the largest number of constraints.

• Heuristic 3: Components appearing in most products first. This heuristic is exactly the same as Chen et al’s approach.

• Heuristic 4: Automatic completion when there is no choice. This heuristic “provides a mechanism to automatically complete the configuration of variables where only one value of their domain is possible […] it also works when a variable has several values on its domain but only one is valid”. In ascending order of computational cost and descending order of constraint propagation capacity, Mazo et al. [9] summarize three approaches to implement Heuristic 4 when the configuration model is encoded as a predicate logic formula: (i) forward-checking; (ii) partial look-ahead; and (iii) full look-ahead (i.e., whereas forward-checking is the fastest algorithm, but produces the most limited form of constraint propagation during search, full look-ahead is the most expensive approach, but gets the best results). In our paper, configuration models are encoded as propositional logic formulas, where a full constraint propagation is computationally feasible. In particular, a configuration model will be encoded as a BDD ψ. To completely propagate a customer decision d, the BDD ψ ∧ d will be computed. Fortunately, this computation only takes linear time on the size of the BDD. That is, the complexity of computing mixing two BDDs ψ₁ and ψ₂ using the apply algorithm proposed by Bryant [33] is O(|ψ₁||ψ₂|), so the complexity of ψ ∧ d is O(|ψ||d|) = O(|ψ| · 1) = O(|ψ|). Instead of considering Heuristic 4 apart, we will use it as a complement to the remaining heuristics by running constraint propagation after every configuration step.

• Heuristic 5: Components required by the latest configured component first. Choose the component that has the largest number of constraints with the past-configured components.

• Heuristic 6: Components that split the problem space in two first. Set first the components that divide the problem space into two parts of approximately the same size. Unfortunately, Mazo et al. [9] do not provide a way to implement this heuristic, which takes into account all model constraints. In particular, Mazo et al. propose a simplification by just using the tree structure of an FD, or the variation points of an orthogonal variability model [34], but not processing the cross-tree constraints.

As will be discussed in Section 4.3, our approach may be thought of as an implementation of Heuristic 6 that, in addition, takes into account all configuration model constraints. In Section 5, it will be shown that our approach provides better outcomes than Heuristics 1, 2, 3 (i.e., Chen’s approach [10]) and 5.

4. Entropy-Based Approach to Sort Configuration Questions

This section presents our heuristic to minimize the number of steps required to configure a derivative from a configuration model. Section 4.1.1. introduces the theoretical background of our approach. As we will see, our heuristic, as other ones summarized in Section 3, requires computing the component probabilities. Section 4.1.2. discusses the scalability limitations of the approach commonly used to compute those probabilities. To overcome such limitations, in Section 4.2, we propose an algorithm that provides an efficient probability computation. Finally, Section 4.3 describes our heuristic.

4.1. Preliminaries

4.1.1. Information Theory

The following definitions were originally introduced by Shannon [8]. Let us start with the concept of entropy.

Definition 1 Let X be a discrete random variable with alphabet$\mathcal{X}$ and probability mass function$\mathrm{Pr}\left(x\right)=\mathrm{Pr}\left\{X=x\right\},x\in \mathcal{X}$; the entropy H of X is defined by Equation (2):

$$H\left(X\right)=-{\displaystyle \sum _{x\in \mathcal{X}}\mathrm{Pr}\left(x\right)\left({\log }_2\mathrm{Pr}\left(x\right)\right)}$$

(2)

Let us present the concept of conditional entropy, which is the entropy of a random variable conditional on the knowledge of another random variable.

Definition 2 Let X and Y be two discrete random variables. The conditional entropy H(X|Y) of X given Y is defined by Equation (3):

$$H\left(X|Y\right)={\displaystyle \sum _{y\in Y}\mathrm{Pr}\left(y\right)H\left(X|Y=y\right)}$$

(3)

Finally, let us introduce the concept of mutual information, also called information gain, which represents the reduction in a variable uncertainty due to another random variable.

Definition 3 Consider two random variables Xand Ywith a joint probability mass function Pr(x, y) and marginal probability mass functions Pr(x) and Pr(y). The mutual information I(X; Y) is defined by Equation (4) as the relative entropy between the joint distribution and the product distribution Pr(x)Pr(y):

$$I\left(X;Y\right)={\displaystyle \sum _{x,y}\mathrm{Pr}\left(x,y\right){\log }_2\frac{\mathrm{Pr}\left(x,y\right)}{\mathrm{Pr}\left(x\right)\mathrm{Pr}\left(y\right)}}$$

(4)

Entropy and mutual information satisfy the following properties that will be used throughout this paper:

(1)

H(X) ≥ 0

(2)

$H\left(X\right)\le {\log }_2\#\mathcal{X}$, with equality if and only if X is distributed uniformly over $\mathcal{X}$ (in this paper, the number of elements of a set S is denoted as #S)

(3)

I(X; Y) = H(X) − H(X|Y) = H(Y) − H(Y|X) = I(Y; X)

4.1.2. Straightforward Approach to Compute Component Probabilities

A widespread approach to support the automated management of configuration models is translating them to propositional logic formulas [3,25], which are processed using off-the-self tools, such as SAT solvers [35] or BDD engines [33]. Table 3 summarizes the translations needed to encode our running example into propositional logic. A more detailed explanation of how to translate feature models into logic may be found in [36]. Equation (5) is the equivalent logic formula to Figure 1.

(5)

Once a configuration model is encoded into a logic formula ψ:

• the total number n₁ of valid derivatives is equivalent to the number of satisfying assignments of ψ (i.e., those that evaluate ψ to be true).

• the number n₂ of valid derivatives that include component c is equivalent to the number of satisfying assignments of ψ ∧ c.

Since the probability of a component is $\frac{n_2}{n_1}$ and the computation of the number of satisfying assignments of a Boolean formula is supported by most BDD engines and SAT solvers (in particular, #SAT counters are a type of SAT solver specifically oriented to compute such a number), a straightforward approach to compute the component probabilities is calling repeatedly a logic engine using ψ ∧ c_i as the input [11]. Unfortunately, this approach has a high computational cost and does not scale for all, but trivial configuration models. While the SAT problem is known to be NP-complete [37], it is widely believed that the #SAT problem is even harder [35]. If n is the number of components, computing the component probabilities requires calling a #SAT solver n times, which is extremely time-consuming. Similarly, computing the number of satisfying assignments with a BDD has computational complexity O(m) [33], where m is the number of nodes of the BDD. Hence, the complexity of computing the component probabilities by calling repeatedly the BDD engine is O(n · m), which is excessively time-consuming for most configuration models.

For instance, it is well known by the car manufacturing community that the first issue of car configurators is performance [38]. Thus, as soon as customers make a configuration choice, they want to find out what the consequences of the choice are. From a marketing perspective, it is unpleasant for customers to wait for several seconds to know whether their requirements are correct or not in terms of configuration. As it will be shown experimentally in Section 5, computing the component probabilities by calling repeatedly a BDD may force the costumer to wait for more than 600 seconds for just a single configuration step!

To overcome the aforementioned scalability limitations, in the following section, we propose a BDD algorithm that computes component probabilities in almost linear time to m.

5. Experimental Evaluation

To test the validity of our approach, we have used two case studies:

(1)

The configuration model provided by the car manufacturing company Renault DVI [14], which deals with the configuration of a family of cars named Renault Megane and is freely available at [15]. We have selected this model because it illustrates the practical applicability of our approach (i.e., instead of using an example made up for academic purposes, our work is tested on a real configuration model that comes from the industry). In addition, the Renault Megane problem is a benchmark of widespread use by the configuration community [39–49].

(2)

The Electronic Shopping model provided by Lau [17], which deals with an electronic commerce platform that allows consumers to directly buy goods or services from a seller over the Internet using a web browser. This benchmark is widely used by the software product line community [26,50,51] and is freely available at [16].

6. Conclusions

To satisfy a wide range of customers, product platforms must provide a high variety of optional components. For this reason, the configuration of all, but trivial, derivatives involves considerable effort in selecting which components they should include, while avoiding violations of the inter-component dependencies and incompatibilities. Our approach enriches existing automated configurators by reducing the number of steps required to configure a valid derivative.

Applying the information theory concept of entropy, our approach takes advantage of the fact that, due to the inter-component constraints, some decisions may be automatically derived from other decisions previously made. Therefore, the order in which decisions are made has a strong influence on the number of decisions required to complete a configuration. Moreover, our approach does not provide a static ordering that the customer is forced to follow. On the contrary, it suggests orderings dynamically, reacting to the customer decisions. In addition, we have proposed an algorithm that efficiently computes the variable probabilities of a Boolean formula, supporting in this way not only our approach, but also other methods proposed in related work.

The Renault Megane and Electronic Shopping configuration benchmarks have been used to test the applicability of our approach and its effectiveness. In particular, it has been shown that our approach needs less configuration steps than related work.