Explanations play an important role in the context of feature model (FM) configuration. First, they can assure the interpretability of the calculated solutions (configurations) as a result of a feature model configuration process. Beyond this, explanations can support engineers (developers) of feature models in the identification of issues in the model, i.e., to figure out as to why on a semantic level the feature model does not fully represent the existing product (service) domain knowledge. In this paper, we discuss diferent basic explanation scenarios in the context of feature model development and feature model configuration. We show how these explanations can be supported on the basis of the concepts of conflict detection and model-based diagnosis.
Feature models (FMs) can be used for the representation of commonality and variability properties of highly-variant artifacts such as physical products and software [1, 2, 3, 4, 5, 6]. Formal representations of feature models such as SAT problems [7] and constraint satisfaction problems (CSPs) [8, 9] are often used to find a solution for a given feature model configuration task and – beyond that – for supporting diferent types of analysis operations used to assure the well-formedness and semantic correctness of feature models [3, 10]. Compared to the representation as SAT problem, CSPs allow for a more lfexible knowledge representation, for example, in terms of a direct representation of logical equivalence properties and implications [4].
Independent of the used FM knowledge representation, it is important to provide users with explanations [4, 11, 12, 13, 14]. Such explanations can serve diferent purposes ranging from assuring interpretability for the user, increasing the trust level of a user, enhancing a user’s domain knowledge, to persuading users to include/exclude specific features into/from an FM configuration [12, 15, 16, 17, 18, 19, 20, 21]. In this paper, we focus on the aspect of interpretability. We discuss diferent explanation scenarios in the context of feature model development and feature model configuration. For example, in the context of feature model development and maintenance, a modeler needs to know the set of features responsible for the violation of a specific property (e.g., void feature models or dead features in feature models). Furthermore, users of an FM configurator are interested as to why specific features have been included but also why other features have been excluded unexpectedly (the counterfactual case). In the following, we discuss diferent explanation scenarios and show how standard QuickXPLain-style conflict detection [ 22, 23] and diagnosis [24] algorithms can be applied to generate explanations and corresponding repairs in the case of inconsistencies.
The major contributions of our paper are the following: (
The remainder of this paper is organized as follows. In Section 2, we introduce an example feature model that serves as a working example throughout the paper. Thereafter, in Section 3, we introduce two basic algorithms supporting the tasks of conflict detection and diagnosis. In Section 4, we show how these algorithms can be applied to support diferent FM-related explanation scenarios. A discussion of threats to validity is provided in Section 5. In Section 6, the paper is concluded with an overview of research issues.
In the following, we present an example feature model from the domain of survey software configuration , which will serve as a running example throughout this paper (see Figure 1).
The features in this model are arranged hierarchically including the following relationships: (
To enable FM configuration, feature models must be translated into a formal representation. Common approaches for this translation include SAT problems [26, 27], answer set programs (ASPs) [28], and constraint satisfaction problems (CSPs) [8, 29, 30]. In this paper, we adopt CSPs as the formal representation for feature models. For a detailed discussion of the rules governing the translation of feature models into logic-based representations, we refer to [4, 8]. The constraint-based representations we generate in this paper follow these established translation rules. 3. Conflict Detection and Model-based Diagnosis In Table 1, we introduce a CSP-based formalization of the FM shown in Figure 1. In this formalization, 0 is the root constraint (part of every feature model) that ensures that in each FM configuration at least one feature is included, i.e., no empty feature model configurations are allowed.
Based on this example CSP (Table 1), we now introduce the concept of a feature model configuration task (see Definition 1) and a corresponding feature model configuration (see Definition 2) [4]. Definition 1. An FM configuration task is defined as a constraint satisfaction problem ( , ), where is a set of Boolean variables (features) (with domain () = {true, false}), and = ∪ is a set of constraints. Here, = {0 . . . } represents a set of domain constraints, and = {+1 . . . } represents a set of user requirements.
In our example, = {0 . . . 8} (see Table 1) and = {9 : = }, meaning that the user has specified ABtesting ( ) to be included in the final configuration.
Definition 2. An FM configuration CONF = {1 = (1), 2 = (2), . . . , = ()} is a set of variable assignments, where () is the value assigned to the variable (feature) . A configuration CONF is considered consistent if (⋃︀ { = ()} ∈ CONF )∪∪ is consistent (i.e., a solution exists). A configuration is complete if every variable in has a corresponding assignment in CONF . Finally, CONF is valid if it is both, consistent and complete.
Example 1. An example configuration could be CONF = { = , = , = , = , = , = , = , = , = }.
However, there are often situations where a configuration is inconsistent with the constraints in the feature model or the feature model constraints are inconsistent resulting in a void feature model. Also, customer requirements can induce an inconsistency with the FM constraints resulting in a situation where no solution can be identified. To deal with such situations, the concepts of conflict sets (see Definition 3) and diagnoses (see Definition 4) are fundamental [ 4]. In the following, these two concepts are formulated with regard to a constraint set which is inconsistent, i.e., no solution could be found for the constraints in .
Definition 3. A conflict set is a set Γ ⊆ with inconsistent(Γ). A conflict set is minimal if ¬∃Γ′ : Γ′ ⊂ Γ and Γ′ is a conflict set.
QuickXPlain For a minimal conflict set to be resolved, only one constraint needs to be deleted from the conflict set. The term minimal conflict set is often used synonymously to the term minimal unsatisfiable subset (MUS) [31]. Minimal conflict sets can be determined on the basis of the QuickXPlain algorithm [22] which determines one minimal conflict set ( Γ) at a time. Given a set of constraints = {1, .., , +1, .., } ( is assumed to be 2 ), if {1, .., } is inconsistent, the QuickXPlain conflict set search will focus on {1, .., } and immediately omit {+1, .., }. In many scenarios, all minimal conflict sets need to be determined. In such a situation, QuickXPlain needs to be combined with a corresponding hitting set directed acyclic graph based approach which helps to determine all minimal conflict sets in a systematic fashion [32].
Definition 4. is a diagnosis.
A diagnosis Δ ⊆ fulfills: consistent( − Δ). Δ is minimal if ¬∃Δ′ : Δ′ ⊂ Δ and Δ′ FastDiag In each case, a minimal diagnosis consists of a set of constraint which – if deleted from – assure that − Δ is consistent. The term minimal diagnosis of often used synonymously to the term minimal correction subset (MCS). Furthermore, the complement of a MCS, i.e., − , is denoted as maximal satisfiable subset (MSS) [31]. Minimal diagnoses (Δ) can be determined with the FastDiag algorithm [24] which is similar to QuickXPlain in terms of the used divide-and-conquer based search strategy. Given a set of constraints = {1, .., , +1, .., } ( is assumed to be 2 ), if {1, .., } is consistent, the FastDiag diagnosis search will focus on {+1, .., } and immediately omit {1, .., }.
In the following, we show how QuickXPlain can be applied to generate explanations in FM
development, maintenance, and configuration contexts. Furthermore, we show how FastDiag can be
applied to generate repairs to recover from unintended (often inconsistent) situations. Note that both
algorithms are standard algorithms in the context of conflict detection and diagnosis. For related
algorithmic/implementation details we refer to [22, 24].
4. Explanations in FM Development and Configuration
We now introduce a schema of how to apply QuickXPlain [22] and FastDiag [24] for creating
explanations and to propose corresponding repair actions where needed. In this context, QuickXPlain(, )
is assumed to return a minimal conflict set Γ where represents a set of constraints that can be used for
explanation purposes and represents the background knowledge, i.e., a set of constraints assumed to
be correct. Furthermore, FastDiag(, ) is assumed to return a minimal diagnosis Δ where represents
a set of constraints to be used for diagnosis purposes and again represents the background knowledge.
In our discussion, we distinguish between the phases of (
Feature Model Development The major focus of feature model development is to identify the set of features relevant for describing the variability properties of the underlying domain and to integrate constraints that specify relevant commonality and variability properties. In the context of FM development and maintenance, analysis operations play a major role in terms of assuring wellformedness properties of the created models [3]. Indicating the violation of a well-formedness rule defined by an analysis operation is of enormous help [ 33]. In this context, explanations can help to further advance the state of practice by supporting more in-depth insights into the reasons of the violation of a well-formedness rule.
While being aware of further analysis operations, we provide a selected set of operations specifically in the need of a constraint solver (configurator) support (see Table 2). Analysis operations in the need of such a reasoning support are also in the need of explanations that help to better understand the (negative) outcome of an analysis operation and to trigger repair actions [4]. Each entry in Table 2 consists of the description of the analysis operation (formulated as a corresponding question), a corresponding explanation (why not?), and a repair in the case that the analysis operation provides a negative answer.
id 1 2 3 4 5 6 is irredundant( ∈ , )? is generalization(, )?
is satisfiable(CONF , )?
The analysis operations included in Table 2 are the following:
(
(
(5) if a generalization between the feature models (the more general one allowing more solutions [4]) and (the more specific one representing a solution-wise subset of ) does not exist, an explanation can indicate those elements (constraints) responsible for a situation where does not represent a superset of . A related diagnosis Δ indicates those elements that need to be deleted from such that the mentioned superset property is fulfilled.
(6) if a configuration CONF is inconsistent with the constraints in , an explanation indicates constraints (i.e., variable value assignments) in CONF that induce an inconsistency with . Furthermore, a diagnosis Δ indicates minimal sets of constraints (assignments) to be deleted from CONF such that consistency with the constraints in can be restored [36].
Table 6 provides an overview of how the discussed analysis operations (see Table 2) can be supported by the conflict detection algorithm QuickXPlain [22] and the diagnosis algorithm FastDiag [24]. Note that these algorithms could also be replaced by other alternatives if conflict set and diagnosis minimality is assured by those algorithms. For example, if () is not fulfilled (i.e., the feature model does not allow the identification of a solution), Γ=QuickXPlain(, ∅) returns a minimal set of elements of as an explanation indicating that those elements are in conflict. Note that more than one such explanation (conflict) could exist in . If this is the case, a hitting set directed acyclic graph (HSDAG) based approach [32] can be applied (in combination with QuickXPlain) to identify all related explanations (minimal conflict sets). If a repair proposal is requested, FastDiag can determine a corresponding diagnosis Δ which expresses a minimal set of elements to be deleted from in order to be able to restore consistency in . In a similar fashion, QuickXPlain and FastDiag can be activated in the other mentioned explanation scenarios.
repair
FastDiag(, ∅) FastDiag(, { = }) FastDiag(, { = })
QuickXPlain(, ) FastDiag(, ) FastDiag(CONF , )
Feature Model Configuration Feature model configuration supports the identification of a decision regarding the inclusion or exclusion of specific features in a configuration. In the context of such (often interactive) configuration sessions, explanations can help the user of a feature model configurator to better understand the reason of a specific feature inclusion or exclusion but also as to why specific features have not been included (i.e., an explanation of the counterfactual case) [37, 12, 17]. Example questions that need to be answered (i.e., explained to users) are shown in Table 7.
id
1
2
3
id
1
2
3
(
(
(3) if the user requirements in do not allow the determination of a solution, an explanation will indicate a subset of requirements that induce an inconsistency with [22]. A diagnosis Δ includes a set of requirements that need to be deleted/adapted to restore consistency. If we assume the existence of the user requirements = {9, 10, 11}, the corresponding explanations are Γ1 and Γ2 with the diagnoses Δ1 and Δ2 indicating a way to resolve the conflicts in Γ1 and Γ2. In this context, Δ1 is a singleton diagnosis, i.e., a diagnosis consisting of the minimal number of elements needed to resolve all existing conflicts. 1Due to the Boolean nature of feature model variables, an adaptation/deletion of a feature always means either to switch from feature inclusion to exclusion or vice-versa.
In this paper, we have shown how to apply consistency-based conflict detection and diagnosis to determine corresponding explanations and repair actions. We are aware of the fact that there are related open issues, for example, instead of deleting constraints from an envisioned superset to assure an entailment relationship with the specialized feature model , we could also think about adding additional constraints to . We regard such open repairs as being beyond the scope of this paper, however, this appears to be a challenging topic for future work. In this paper, we did not conduct performance evaluations of the diferent explanation and repair settings, however, the used algorithms are well-established and have shown to be applicable in various configuration scenarios which we took as a reason for not including another performance evaluation of QuickXPlain and FastDiag.
In this paper, we have shown how to apply conflict detection and diagnosis for the creation of
consistencybased explanations and corresponding repair actions. We have identified two major application scenarios
which are (
The authors used ChatGPT for language refinement and improving readability. All AI-generated suggestions were carefully reviewed and edited by the authors, who take full responsibility for the content of this publication. [3] D. Benavides, S. Segura, A. Ruiz-Cortes, Automated analysis of feature models 20 years later: A literature review, Information Systems 35 (2010) 615–636. [4] A. Felfernig, A. Falkner, D. Benavides, Feature Models: AI-Driven Design, Analysis and Applications, Springer, 2024. doi:10.1007/978-3-031-61874-1. [5] J. Galindo, J. Horcas, A. Felfernig, D. Fernandez-Amoros, D. Benavides, Flama: A collaborative efort to build a new framework for the automated analysis of feature models, in: Proceedings of the 27th ACM International Systems and Software Product Line Conference - Volume B, SPLC ’23, ACM, New York, NY, USA, 2023, pp. 16–19. doi:10.1145/3579028.3609008. [6] K. Kang, S. Cohen, J. Hess, W. Novak, S. Peterson, Feature-oriented Domain Analysis (FODA) –
Feasibility Study, TechnicalReport CMU – SEI-90-TR-21 (1990). [7] J. Gu, P. Purdom, J. Franco, B. Wah, Algorithms for the satisfiability (sat) problem: A survey, in: DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1996, pp. 19–152. [8] D. Benavides, P. Trinidad, A. Cortés, Using constraint programming to reason on feature models, in: W. Chu, N. Juzgado, W. Wong (Eds.), Proceedings of the 17th International Conference on Software Engineering and Knowledge Engineering (SEKE’2005), Taipei, Taiwan, Republic of China, July 14-16, 2005, 2005, pp. 677–682. [9] A. Popescu, S. Polat-Erdeniz, A. Felfernig, M. Uta, M. Atas, V.-M. Le, K. Pilsl, M. Enzelsberger, T. N. T. Tran, An overview of machine learning techniques in constraint solving, J Intell Inf Syst 58 (2022) 91–118. doi:10.1007/s10844-021-00666-5. [10] A. Felfernig, D. Benavides, J. Galindo, F. Reinfrank, Towards Anomaly Explanation in Feature Models, in: Conf WS-2013: 15th International Configuration Workshop (2013), volume 1128, 2013, pp. 117–124. [11] A. Felfernig, M. Schubert, S. Reiterer, Personalized diagnosis for over-constrained problems, in: 23rd International Joint Conference on Artificial Intelligence, IJCAI ’13, AAAI Press, 2013, pp. 1990–1996. [12] A. Felfernig, D. Garber, V.-M. Le, S. Lubos, Causality-based explanations for feature model configuration, in: 19th International Working Conference on Variability Modelling of SoftwareIntensive Systems, VaMoS ’25, ACM, New York, NY, USA, 2025, pp. 86–90. doi:10.1145/3715340. 3715438. [13] S. Lubos, T. N. T. Tran, A. Felfernig, S. Polat Erdeniz, V.-M. Le, LLM-generated Explanations for Recommender Systems, in: 32nd ACM Conference on User Modeling, Adaptation and Personalization, UMAP Adjunct ’24, ACM, New York, NY, USA, 2024, pp. 276–285. doi:10.1145/3631700.3665185. [14] S. Lubos, M. Gartner, A. Felfernig, R. Willfort, Leveraging LLMs to Explain the Consequences of Recommendations, in: 33rd ACM Conference on User Modeling, Adaptation and Personalization, ACM, 2025, pp. 318–322. doi:10.1145/3699682.3728328. [15] A. Felfernig, M. Wundara, T. Tran, S. Polat-Erdeniz, S. Lubos, M. E. Mansi, D. Garber, V. Le, Recommender systems for sustainability: overview and research issues, Frontiers in Big Data 6 (2023). doi:10.3389/fdata.2023.1284511. [16] M. Hentze and T. Pett and T. Thüm and I. Schaefer, Hyper Explanations for Feature-Model Defect Analysis, in: 15th International Working Conference on Variability Modelling of SoftwareIntensive Systems, VaMoS’21, Association for Computing Machinery, New York, NY, USA, 2021. doi:10.1145/3442391.3442406. [17] D. Kramer, C. Sauer, T. Roth-Berghofer, Towards explanation generation using feature models in software product lines, in: 9th Workshop on Knowledge Engineering and Software Engineering, CEUR, 2013, pp. 13–23. URL: https://ceur-ws.org/Vol-1070/. [18] L. Ochoa, O. González-Rojas, T. Thüm, Using decision rules for solving conflicts in extended feature models, in: ACM SIGPLAN International Conference on Software Language Engineering, Association for Computing Machinery, New York, NY, USA, 2015, pp. 149–160. doi:10.1145/ 2814251.2814263. [19] N. Tintarev, J. Masthof, A survey of explanations in recommender systems, ICDEW ’07, IEEE
Computer Society, USA, 2007, pp. 801–810. doi:10.1109/ICDEW.2007.4401070. [20] T. Tran, S. Polat Erdeniz, A. Felfernig, S. Lubos, M. El Mansi, V. Le, Less is more: Towards sustainability-aware persuasive explanations in recommender systems, in: Proceedings of the 18th ACM Conference on Recommender Systems, RecSys ’24, Association for Computing Machinery, New York, NY, USA, 2024, p. 1108–1112. doi:10.1145/3640457.3691708. [21] T. Tran, A. Felfernig, V. Le, An overview of consensus models for group decision-making and group recommender systems, User Modeling and User-Adapted Interaction 34 (2023) 489–547. doi:10.1007/s11257-023-09380-z. [22] U. Junker, QuickXPlain: preferred explanations and relaxations for over-constrained problems, in: 19th National Conference on Artifical Intelligence, AAAI’04, AAAI Press, 2004, pp. 167–172. [23] O. A. Tazl, C. Tafeit, F. Wotawa, A. Felfernig, DDMin versus QuickXplain - An Experimental Comparison of two Algorithms for Minimizing Collections, in: R. Peng, C. E. Pantoja, P. Kamthan (Eds.), 34th International Conference on Software Engineering and Knowledge Engineering, KSI Research Inc., 2022, pp. 481–486. doi:10.18293/SEKE2022-172. [24] A. Felfernig, M. Schubert, C. Zehentner, An eficient diagnosis algorithm for inconsistent constraint sets, AI for Engineering Design, Analysis, and Manufacturing (AIEDAM) 26 (2012) 53–62. [25] V. Le, C. Silva, A. Felfernig, D. Benavides, J. Galindo, T. Tran, FastDiagP: an algorithm for parallelized direct diagnosis, AAAI’23/IAAI’23/EAAI’23, AAAI Press, 2023. doi:10.1609/aaai. v37i5.25792. [26] C. Gomes, H. Kautz, A. Sabharwal, B. Selman, Satisfiability Solvers, Handbook of Knowledge
Representation (2008) 89–134. [27] M. Mendonça, A. Wasowski, K. Czarnecki, SAT-based analysis of feature models is easy, in: D. Muthig, J. McGregor (Eds.), Software Product Lines, 13th International Conference, SPLC 2009, San Francisco, California, USA, August 24-28, 2009, Proceedings, volume 446 of ACM International Conference Proceeding Series, ACM, 2009, pp. 231–240. [28] V. Myllärniemi, J. Tiihonen, M. Raatikainen, A. Felfernig, Using Answer Set Programming for Feature Model Representation and Configuration, in: 16th International Workshop on Configuration, CEUR, Novi Sad, Serbia, 2014, pp. 1–8. [29] A. Falkner, G. Friedrich, A. Haselböck, G. Schenner, H. Schreiner, Twenty-five years of successful application of constraint technologies at siemens, AI Mag. 37 (2016) 67–80. doi:10.1609/aimag. v37i4.2688. [30] T. W. F. Rossi, P. van Beek, Handbook of Constraint Programming, Elsevier, 2006. [31] S. Gupta, B. Genc, B. O’Sullivan, Explanation in constraint satisfaction: A survey, in: Z.-H. Zhou (Ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI21, International Joint Conferences on Artificial Intelligence Organization, 2021, pp. 4400–4407. doi:10.24963/ijcai.2021/601, survey Track. [32] R. Reiter, A theory of diagnosis from first principles, Artificial Intelligence 32 (1987) 57–95. [33] M. Kowal, S. Ananieva, T. Thüm, Explaining anomalies in feature models, SIGPLAN Not. 52 (2016) 132–143. doi:10.1145/3093335.2993248. [34] R. Bakker, F. Dikker, F. Tempelman, P. Wogmim, Diagnosing and solving over-determined constraint satisfaction problems, in: Proceedings of IJCAI-93, Morgan Kaufmann, 1993, pp. 276–281. [35] V. Le, A. Felfernig, M. Uta, T. Tran, C. Silva, WipeOutR: automated redundancy detection for feature models, in: 26th ACM International Systems and Software Product Line Conference - Volume A, SPLC ’22, ACM, New York, NY, USA, 2022, pp. 164–169. doi:10.1145/3546932.3546992. [36] J. White, D. Benavides, D. Schmidt, P. Trinidad, B. Dougherty, A. Ruiz-Cortes, Automated diagnosis of feature model configurations, Journal of Systems and Software 83 (2010) 1094–1107. [37] C. Dubslaf, K. Weis, C. Baier, S. Apel, Causality in configurable software systems, in: 44th International Conference on Software Engineering, ICSE ’22, Association for Computing Machinery, New York, NY, USA, 2022, pp. 325–337. doi:10.1145/3510003.3510200. [38] G. Friedrich, Elimination of spurious explanations, in: 16th European Conference on Artificial Intelligence, ECAI’04, IOS Press, NLD, 2004, pp. 813–817.