Explanations for over-constrained problems using QuickXPlain with speculative executions

Cristian Vidal [email protected] Alexander Felfernig alexander[email protected] Jos´ e Galindo [email protected] M¨usl¨um Atas [email protected] David Benavides [email protected] 1Departamento de Administraci´ on, Universidad Cat´ olica del Norte, Antofagasta, Chile 2Institute of Software Technology, Graz University of Technology, Graz, Austria 3Computer Languages & Systems, ETSI Inform´ atica, University of Seville, Sevilla, Spain Explanations for over-constrained problems using QuickXPlain with speculative executions Cristian Vidal1 · Alexander Felfernig2 · Jose´ Galindo3 · M ¨usl ¨um Atas2 · David Benavides3 Received: 10 December 2020 / Revised: 27 August 2021 / Accepted: 30 August 2021 / Published online: 6 November 2021 © The Author(s) Abstract Conflict detection is used in various scenarios ranging from interactive decision making (e.g., knowledge-based configuration) to the diagnosis of potentially faulty models (e.g., using knowledge base analysis operations). Conflicts can be regarded as sets of restrictions (constraints) causing an inconsistency. Junker’s QUICKXPLAIN is a divide-and-conquer based algorithm for the detection of preferred minimal conflicts. In this article, we present a novel approach to the detection of such conflicts which is based on speculative programming. We introduce a parallelization of QUICKXPLAIN and empirically evaluate this approach on the basis of synthesized knowledge bases representing feature models. The results of this evaluation show significant performance improvements in the parallelized QUICKXPLAIN version. Keywords Speculative programming · Conflict detection · Explanations · Constraint solving · Configuration · Diagnosis · Feature models 1 Introduction Conflict detection is used in many applications of constraint-based representations (and beyond). Examples thereof are feature modeling (Benavides et al., 2005)andknowledgebased configuration (Felfernig et al., 2014; Stumptner, 1997), where users define requirements (feature selections) and conflict detection is in charge of figuring out minimal sets of potential changes to the given requirements which help to restore consistency (if the underlying reasoning engine is not able to find a solution). Further example applications of conflict detection range from recommender systems (Felfernig & Systems, 2008; Ricci et al., 2011;Tranetal.,2021; Vecchio et al., 2021), model-based diagnosis of hardware designs (Friedrich et al., 1999) and knowledge bases (Felfernig et al., 2004;Leetal.,2021), the analysis of spreadsheets (Schmitz & Jannach, 2017), software requirements prioritization (Felfernig, 2021), to the analysis of feature models (Benavides et al., 2010). Especially in interactive settings, there is often a need to identify preferred conflicts (Horcas et al., 2018; Junker, 2004; O’Sullivan et al., 2007; Rossi et al., 2011;Walsh,2007), for example, users of a car configurator or a camera recommender who have strict preferences regarding the upper price limit, are more interested in relaxations related to technical features (e.g., related to the availability of a skibag in a car or the availability of a wide-aperture lens in a pocket camera). Conflict detection helps figuring out combinations of constraints in the knowledge base that are responsible for an inconsistency. QUICKXPLAIN is such a conflict detection algorithm which is frequently used and works for constraint-based representations, description logics, and SAT solvers (Junker, 2004). The algorithm is based on a divide-and-conquer approach where consistency analysis operations are based on the division of a constraint set C={c1..cm}into two subsets Ca={c1..ck}and Cb={ck+1..cm}assuming, for example, k= m 2.IfCbis inconsistent, the consideration set Ccan be reduced by half since Ca must not be analyzed anymore (at least one conflict exists in Cb). Depending on the QUICKXPLAIN variant, either Caor Cbis checked for consistency. Based on a lexicographical constraint ordering, QUICKXPLAIN determines one preferred minimal conflict set at a time. Conflict detection is often combined with conflict resolution which helps to resolve all existing conflicts in a model (or a knowledge base). In this context, the minimality (irreducability) of conflict sets is important since this allows to resolve each conflict by simply deleting one of the elements in the conflict set. The elements to be deleted to restore global consistency are denoted as hitting set (a diagnosis) and can, for example, be determined on the basis of a hitting set directed acyclic graph (Reiter, 1987). Although QUICKXPLAIN is an efficient solution in many scenarios, there are many cases where computing preferred conflict sets becomes inefficient, for example, when it comes to the analysis of large-scale feature models (Bordeaux et al., 2009;D ´ ıaz et al., 2014; Gent et al., 2018; Hamadi & Sais, 2018; Marques-Silva et al., 2013; Varela-Vaca et al., 2019). In this article, we present a parallelized version of QUICKXPLAIN that is based on the idea that some expensive tasks of the algorithm can be carried out earlier following the principles of speculative programming (Burton, 1985). Although the principles of speculative programming are not new, with the appearance of modern CPUs with parallel computation capabilities, some speculative approaches are now practically possible. Overall, the speculative conflict detection approach presented in this paper follows the idea of predicting potentially relevant consistency checks needed by the conflict detection algorithm and improving runtime performance by executing the predicted consistency checks in a parallelized fashion. 492 The major contributions of this article are the following. First, we show how to parallelize conflict detection on the basis of a flexible look-ahead strategy that scales depending on the number of available computing cores. Second, we show how to integrate the proposed approach with the standard QUICKXPLAIN algorithm that is often used in constraint-based applications. Third, we show the applicability and improvements of our approach on the basis of performance evaluations. Finally, we point out in which way the proposed approach can help to improve the performance of existing diagnosis approaches. This article is an extended version of Vidal et al. (2020) including a working example from the domain of feature modeling, a more in-depth discussion of related and future work, and an extended version of the parallelized version of the QUICKXPLAIN (Junker, 2004) algorithm. We evaluate our speculative programming version of QUICKXPLAIN in the context of inconsistent feature model configurations of randomly generated large-scale feature models and configurations using a generation tool (Galindo & Benavides, 2019). With our approach, we improve the performance of conflict detection tasks scaling with the available cores of CPUs, making it possible to efficiently solve more complex conflict detection problems. The obtained results show a significant gain in performance and general scalability of parallelized QUICKXPLAIN with the number of available CPU cores. The remainder of this article is organized as follows. In Section 2, we summarize related work while emphasizing on the novelty of our approach. In Section 3, we introduce the basic idea of Junker’s QUICKXPLAIN algorithm using a working example. Thereafter, in Section 4we introduce a parallelized variant of the algorithm. In Section 5,weanalyze the proposed approach and report the results of a performance evaluation which shows significant improvements compared to standard QUICKXPLAIN. In Section 6, the article is concluded with a discussion of future work. 2 Related work Research on algorithms for parallelization, conflict detection, and applications thereof can be summarized as follows. Solution search Due to the increasing size and complexity of knowledge bases, there is an increasing need to further improve the performance of solution search (Bordeaux et al., 2009;Gentetal.,2018; Hamadi & Sais, 2018). Parallelizations of algorithms in these scenarios have been implemented in different contexts. Approaches to parallelization have, for example, been proposed on the reasoning level (Bordeaux et al., 2009) where the determination of a solution is based on the idea of identifying subproblems which can be solved to some degree independently by the available cores. Due to today’s multi-core CPU architectures, such parallelizations become increasingly popular since they help to better exploit the offered computing resources. Conflict detection As already mentioned, the efficient determination of minimal conflicts is a core requirement in many application settings (Jannach et al., 2015). Especially in the context of constraint-based reasoning scenarios, the identification of minimal conflict sets is frequently based on QUICKXPLAIN (Junker, 2004). In contrast to sequential approaches (Bakker & Dikker, 1993), QUICKXPLAIN follows a divide-and-conquer based strategy that helps to significantly reduce the number of needed consistency checks. Although the algorithm is often used to support users in interactive settings, the guarantee of efficient runtimes is often quite challenging. In this article, we propose an algorithm that enables parallelized 493 conflict detection and thus helps to significantly improve the runtime performance of conflict detection. In contrast to existing work, our approach supports the parallelization of conflict detection which is the precondition for conflict resolution (performed on the basis of model-based diagnosis (de Kleer & Williams, 1987; Reiter, 1987)).Basedontheprinciples of speculative programming (Burton, 1985), our approach allows the prediction of consistency checks that will be needed in future algorithmic steps and can be pre-calculated in a parallelized fashion. Conflict resolution Given a set of (minimal) conflicts identified by a conflict detection algorithm, conflict resolution can be used to identify corresponding sets of (minimal) diagnoses (de Kleer & Williams, 1987; Marques-Silva et al., 2013; Reiter, 1987;Wotawa,2001). For instance, (Jannach et al., 2015;2016) propose an approach to parallelize the computation of hitting sets (diagnoses). In their approach, Reiter’s approach to model-based diagnosis is parallelized by a level-wise expansion of a breadth-first search tree with the goal of computing minimal (cardinality) diagnoses. On each level, different (minimal) conflict sets are determined in parallel, however, the determination of individual conflict sets is still a sequential process (based on QUICKXPLAIN Junker, 2004). In an extended version, (Jannach et al., 2016) replace the level-wise expansion with a full parallelization of hitting set determination with additional mechanisms to ensure the minimality of proposed diagnoses. In contrast to the work presented in this article, existing approaches (Jannach et al., 2015) focus on the parallelization of the conflict resolution (diagnosis) step but do not offer solutions to increase the efficiency of conflict detection itself. Our parallelized version of QUICKXPLAIN shows exactly the same behavior in terms of calculated solutions as the sequential version and thus can help to improve the performance of conflict resolution. Model analysis Model analysis (see, e.g., Galindo et al., 2019) is a computer-aided process that (1) translates model constraints into a logical representation (e.g., SAT or CSP), (2) applies some defined operations by the use of off-the-shelf solvers or specific programming solutions, and (3) provides feedback on specific model properties as a process result. Feature model diagnosis is a model analysis task for resolving conflicts in feature models in order to be able to come up with an error-free feature model or configuration (Felfernig et al., 2013). For instance, if a user wants to select and deselect a set of features but some selections and de-selections are incompatible, diagnosis (conflict resolution) would suggest which features have to be selected/deselected from the original configuration to fix the problem and convert the original inconsistent configuration into a valid one (White et al., 2010). Further example applications of model-based diagnosis in the context of feature model analysis are the identification of minimal sets of constraints responsible for the existence of dead features or the identification of minimal sets of constraints responsible for a void feature model. A major precondition for supporting such kinds of analysis operations are conflict detection algorithms such as QUICKXPLAIN that help to determine minimal conflicts in the underlying model. In the line of feature model analysis, the automated debugging of faulty or inconsistent knowledge bases plays a major role in various industrial scenarios (Fleischanderl, 2002). An approach to the automated debugging of inconsistent knowledge bases is introduced in Bakker and Dikker (1993). A variant thereof that focuses on the automated analysis of configuration knowledge bases is discussed in Felfernig et al. (2004). Further applications Conflict detection and diagnosis have numerous applications in industrial scenarios. For example, Felfernig et al. (2006) discuss the application of the concepts of model-based diagnosis (Reiter, 1987) for the analysis of conflict-inducing user 494 requirements (in the domain of financial services recommender systems), i.e., minimal sets of requirements defined by the user that should be changed in order to restore consistency with the underlying knowledge base. The application of model-based diagnosis concepts in knowledge-based configuration scenarios (telecommunication systems) is presented in Fleischanderl (2002). Different applications of model-based diagnosis in the context of Internet of Things (IoT) scenarios are discussed in Polat et al. (Felfernig et al., 2019). Furthermore, Felfernig et al. (2018) present applications in the context of group decision support on the basis of recommender systems. In these scenarios, group members articulate their individual preferences which can become inconsistent. An example thereof is software release planning, where stakeholders could have different preferences regarding the assignment of requirements to corresponding software releases. In this context, the role of conflict detection and diagnosis is to figure out minimal sets of preferences that have to be adapted in order to restore consistency and to assure consensus in the group. Finally, there exist different applications of conflict detection and model-based diagnosis in the context of reconfiguration. Reconfiguration refers to situations where an existing configuration has to be adapted in order to fulfill new requirements (Felfernig et al., 2018). Applications thereof are the reconfiguration of network infrastructures, the reconfiguration of production schedules, and the reconfiguration of data transfer protocols in the context of Internet of Things (IoT) scenarios (Felfernig et al., 2019). 3 Calculating minimal conflicts In the following, we will introduce our approach to parallelized conflict detection on the basis of constraint-based knowledge representations (Tsang, 1993). First, we provide some basic definitions and examples to understand the approach. Aconflict set can be defined as a minimal set of constraints that is responsible for an inconsistency, i.e., a situation in which no solution can be found for a given constraint satisfaction problem (CSP) (see Definitions 1–2). Definition 1 AConstraint Satisfaction Problem (CSP) is a triple (V, D, C) with a set of variables V={v1..vn}, a set of domain definitions D={dom(v1)..dom(vn)}, and a set of constraints C={c1..cm}. Definition 2 Assuming the inconsistency of C,aconflict set can be defined as a subset CS ⊆C:CS is inconsistent. CS is minimal if ¬∃CS:CS⊂CS. Figure 1shows an example of a feature model of a car (configuration). Dark grey features are features that are regarded as user-selected while features with a white background are features that are regarded as undesired, i.e., should not be part of the configuration. In the feature model and selected configuration (features with dark grey background) there is a conflict: if the user selects skibag, the car type has to be (s)uv and not (c)city.However,(c)ity has been selected. Consequently, the selections in Fig. 1induce a conflict. It is well known that a feature model can be mapped to a CSP (Benavides et al., 2005; Felfernig et al., 2014). To make it simpler and more general, in the rest of the article we will refer directly to the derived CSP from the feature model of Fig. 1. 495 Fig. 1 Example feature model of a configurable car. Features with grey background represent selected features. Since the feature skibag is selected (constraint c2) and the inclusion of skibag requires the inclusion of suv (constraint c6), the inclusion of city (constraint c4) triggers an inconsistency Simple examples of a CSP and a corresponding conflict set are the following (see Examples 1–2).1Please note that in order to reduce the number of needed constraints, we did not follow the standard approach of translating feature models to a corresponding CSP (Benavides et al., 2005) but defined the leaf nodes of the feature model as domain values of the corresponding parent features, for example, dom(cartype) =[(s)uv, (c)ity]. Example 1 An example of a CSP for car feature model (inspired by the model of Fig. 1)is the following: V={car, cartype, f uel, pdc, color, skibag}, D={dom(car) =[y,n],dom(cartype)=[(s)uv, (c)ity], dom(fuel) =[(p)etrol, (d)iesel],dom(pdc)=[y,n], dom(color) =[b, r, g],dom(skibag)=[y,n]} C={c1:fuel =d,c2:skibag =y,c3:color =b, c4:cartype =c, c5:pdc = y,c6:skibag =y→cartype =s, c7:cartype =c→color =b, c8:car =y}. It is convenient to distinguish between a consistent background knowledge Bof constraints that cannot be relaxed (in our case, B={c6,c 7,c 8})andaconsideration set Cof relaxable constraints (in our case, requirements C={c1..c5}). In our example, we focus on detecting conflicts in the feature selections (defined feature inclusions and exclusions) but not in the constraints of the feature model which we assume to be consistent. Example 2 In Example 1, there is one minimal conflict which is CS ={c2,c 4},since {c2,c 4}⊆Cand inconsistent (CS ∪B). Furthermore, CS is minimal since there does not 1Note that this representation can be easily translated into a specific solver representation – see, for example, choco-solver.org. 496 exist a CSs.t. CS⊂CS. The execution trace of QUICKXPLAIN for this working example is depicted in Fig. 2. QUICKXPLAIN (Junker, 2004) (a variant is shown in Algorithms 1 and 2) supports the determination of minimal (irreducible) conflicts in a given set of constraints (C). QUICKXPLAIN is activated if the background knowledge B(often assumed to be empty or a consistent set of constraints) is inconsistent with the set of constraints C(we assume this consistency check to be performed by a direct solver call). The core algorithm is implemented in the function QX (Algorithm 2) that determines a minimal conflict which is a minimal subset of the constraints in Cwith the conflict set property. Fig. 2 QX execution trace for C={c1..c5}and B={c6,c 7,c 8}assuming a minimal conflict set CS ={c2,c 4}. Underlined Bs denote QX consistency checks. For example, in the incarnation [2] of the QX function, the consistency check activated is {c3..c5,c 6,c 7,c 8} 497 The function QX (Algorithm 2) focuses on isolating those constraints that are part of a minimal conflict. If Cincludes only one element (C={cα}), this element can be considered as element of the conflict - this is due to the invariant property inconsistent(C∪B). If Bis consistent and Chas more than one element, Cis divided into two separate sets, where (in our QX variant) the second part (Cb) is added to Bin order to analyse further elements of the conflict. The function QX activates a consistency check (INCONSISTENT) to figure out whether the considered background knowledge is inconsistent, i.e., no solution exists. The variable Bδ indicates which constraints have been added to B. In many of the aforementioned application scenarios, there exists an exponential number of conflicts and ways to resolve a conflict (Junker, 2004). Especially in interactive scenarios, it is extremely important to identify preferred conflicts, i.e., conflicts with a high probability of being the basis of a relaxation acceptable for the user. For example, if a user is strongly interested low-priced digital cameras, a conflict set that includes a price limit might be of low relevance for the user (since the user is not willing to change the price limit). QUICKXPLAIN (Junker, 2004) supports the determination of preferred conflicts. Although our discussions focus on constraint-based representations, the approach can be applied to any kind of satisfiability problem such as propositional satisfiability (SAT) and description logics (DL). We assume monotonic satisfiability (see Proposition 1). Proposition 1 If a solution for a CSP satisfies all constraints ci∈Cthen it also satisfies every proper subset C⊂C. 498 QUICKXPLAIN determines one minimal preferred explanation (conflict) at a time which includes constraints one might be willing to relax. In the line with Junker (2004), an explanation Xis preferred over an explanation Yunder the following condition (see Definition 3). Definition 3 We define a total order <on the constraints in C={c1..cm}which is represented as [c1<c 2<.. <c m].Ifci<c j, i.e., the importance of ciis higher than cj,then i<j.IfXand Yare two lexicographical constraint orderings of c1..cn,Yis preferred over X(Y> lex X)iff ∃k:ck∈X−Yand X∩{ck−1..c1}=Y∩{ck−1..c1}. Example 3 Given the constraint ordering [c3<c 4<c 5<c 6]and two binary conflict sets X={c3,c 4}and Y={c4,c 5},Yis preferred over Xsince c3∈X−Ywith X∩{c2,c 1}= Y∩{c2,c 1}. 4 Parallelizing QUICKXPLAIN Our approach to parallelize the consistency checks in QX substitutes the direct solver call INCONSISTENT(B) in QX with the activation of a lookahead function (QXGEN)inwhich consistency checks are not only triggered to directly provide feedback to QX requests, but also to be able to provide fast answers for consistency checks potentially relevant in upcoming states of a QX instance. We follow the principles of speculative programming (Burton, 1985): we start calculating consistency checks that could be useful in the future. The advantage is that we can anticipate resource-intensive reasoning tasks. The drawback is that we use some computation resources that will be wasted in the case that the pre-calculation is finally not used. Therefore, the challenge in this kind of techniques is to find algorithms able to anticipate as many reusable calculations as possible while reducing the calculation tasks that are not reusable. Finding a good algorithm to speculate over possible parallelized tasks is not evident and different approaches could be taken. In our case, we could follow a naive approach that would randomly merge elements from Cand add consistency checks to a consistency stack for later reuse. However, such an approach is likely to be inefficient because there will be many consistency checks that would be activated but never be used. Checking randomly generated constraint sets never relevant for QUICKXPLAIN would be counter-productive and thus slow down conflict search. In the parallelized variant of QUICKXPLAIN that we propose, consistency checking is activated by QX with INCONSISTENT(C, B, Bδ) (see Algorithm 3). This also activates QXGEN (see Algorithm 4) that starts to generate and trigger (in a parallelized fashion) further consistency checks that might be of relevance in upcoming QX phases. For describing QXGEN, we employ a two-level ordered set notation which requires, for example, to embed the QX Binto {B},etc.InQXGEN,C,Bδ,andBare interpreted as ordered sets. 499 parallelized variant of QUICKXPLAIN helps to exploit such architectures and provide efficient conflict detection especially when dealing with complex knowledge bases. With this approach, we help to boost the performance of various knowledge-based applications and thus make them more accessible especially in the context of interactive settings. On the basis of the work presented in this article, our goals for future research are the following. First, a weakness of the current approach is the fact that also consistency checks are triggered which might not be needed in future steps of the algorithm. Minimizing the number of irrelevant consistency checks will also be a major objective of our future work. Second, we will integrate our approach into divide-and-conquer based diagnosis approaches (see, e.g., Felfernig et al., 2012). Related algorithms follow a solution approach similar to QUICKXPLAIN and thus can also profit from parallelization on the basis of intelligent lookahead search strategies as presented in this article. Furthermore, we will analyze in which way the predictions of consistency checks can be made more precise, for example, by learning from already completed user interactions. Also, some more complex knowledge bases could be incorporated in our runtime analyses. We conjecture that the improvement in performance can be even greater than the ones shown when having more complex knowledge bases with more complex conflict sets. We intend to extract complex knowledge bases from public repositories and extend our analyses. Our approach is a door-opener for a future line of research where parallelization can leverage explanation efficiency. Acknowledgements This work has been partially funded by the EU FEDER program, the PARXCEL project (880657) funded by the Austrian Research Promotion Agency, the MINECO project OPHELIA (RTI2018- 101204-B-C22), the TASOVA network (MCIU-AEI TIN2017-90644-REDT), and the Junta de Andalucia METAMORFOSIS project. We want to thank Jes´us Gir´ aldez from the University of Granada as well as Rafael Corchuelo and Mayte G´ omez–L´ opez from the University of Sevilla for providing feedback in early stages of this research. Material The software, material and results used during the runtime analysis can be accessed through https://doi.org/10.5281/zenodo.3825090 References Acher, M., Collet, P., Lahire, P., & France, R. (2013). Familiar: A domain-specific language for large scale management of feature models. Science of Computer Programming,78(6), 657–681. Alf´ erez, M., Acher, M., Galindo, J. A., Baudry, B., & Benavides, D. (2019). Modeling variability in the video domain Language and experience report. Software Quality Journal,27(1), 307–347. Bakker, R., & Dikker, F. (1993). Diagnosing and Solving Over-determined Constraint Satisfaction Problems. In 13Th intl. Joint conference on artificial intelligence (IJCAI’93) (pp. 276–281). France: Chamb´ ery. Batory, D. (2005). Feature models, grammars, and propositional formulas. In Intl. conference on software product lines (pp. 7–20). Springer. Benavides, D., Ruiz-Cort´ es, A., & Trinidad, P. (2005). Automated reasoning on feature models. In LNCS Advanced information systems engineering: 17th Intl, Conference, CAiSE 2005, (Vol. 3520 pp. 491– 503). Benavides, D., Segura, S., & Ruiz-Cortes, A. (2010). Automated analysis of feature models 20 years later A literature review. Information Systems,35, 615–636. Bordeaux, L., Hamadi, Y., & Samulowitz, H. (2009). Experiments with Massively Parallel Constraint Solving. In 21St Intl. Joint conference on artifical intelligence (pp. 443–448). USA: Morgan Kaufmann Publishers. Burton, F. (1985). Speculative computation, parallelism, and functional programming. IEEE Transactions on Computers,C-34(12), 1190–1193. de Kleer, J., & Williams, B. (1987). Diagnosing multiple faults. Artificial Intelligence,32(1), 97–130. 506 D´ ıaz, J., P´ erez, J., & Garbajosa, J. (2014). Agile product-line architecting in practice: A case study in smart grids. Information and Software Technology,56(7), 727–748. Doux, G., Albert, P., Barbier, G., Cabot, J., Del Fabro, M., & Lee, S. (2011). An mde-based approach for solving configuration problems An application to the eclipse platform. In European conference on modelling foundations and applications (pp. 160–171). Springer. Felfernig, A. (2021). AI techniques for software requirements prioritization. In M. Kalech, R. Abreu, & M. Last (Eds.) Artificial intelligence methods for software engineering (pp. 29–47). World Scientific. Felfernig, A., Benavides, D., Galindo, J., & Reinfrank, F. (2013). Towards anomaly explanation in feature models. In 15Th intl. configuration workshop (pp. 117–124). Felfernig, A., Boratto, L., Stettinger, M., & Tkalcic, M. (2018). Group Recommender Systems – An Introduction. Berlin: Springer. Felfernig, A., & Systems, R. Burke. (2008). Constraint-based Recommender Technologies and Research Issues. In ACM intl. conference on electronic commerce (ICEC’08) (pp. 17–26). Austria: Innsbruck. Felfernig, A., Friedrich, G., Jannach, D., & Stumptner, M. (2004). Consistency-based Diagnosis of Configuration Knowledge Bases. Artificial Intelligence,152(2), 213–234. Felfernig, A., Friedrich, G., Jannach, D., & Zanker, M. (2006). An integrated environment for the development of knowledge-based recommender applications. Intelligence Journal of Electronic Commerce (IJEC),11(2), 11–34. Felfernig, A., Hotz, L., Bagley, C., & Tiihonen, J. (2014). Knowledge-based Configuration - From Research to Business Cases. Burlington: Morgan Kaufmann. Felfernig, A., Polat-Erdeniz, S., Uran, C., Reiterer, S., Atas, M., Tran, T., Azzoni, P., Kiraly, C., & Dolui, K. (2019). An overview of recommender systems in the internet of things. Journal of Intelligent Information Systems,52(2), 285–309. Felfernig, A., Schubert, M., & Zehentner, C. (2012). An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets. Artificial Intelligence for Engineering Design, Analysis and Manufacturing,26(1), 53– 62. Felfernig, A., Walter, R., Galindo, J., Benavides, D., Erdeniz, S., Atas, M., & Reiterer, S. (2018). Anytime Diagnosis for Reconfiguration. Journal of Intelligent Information Systems,51(1), 161–182. Fleischanderl, G. (2002). Suggestions from the software engineering practice for applying Consistency- Based diagnosis to configuration knowledge bases. In 13Th Intl. workshop on principles of diagnosis (DX-02) (pp. 33–35). Austria: Semmering. Friedrich, G., Stumptner, M., & Wotawa, F. (1999). Model-based Diagnosis of Hardware Designs. Artificial Intelligence,111(1–2), 3–39. Galindo, J., & Benavides, D. (2019). Towards a new repository for feature model exchange. In C. Cetina, O. D´ ıaz, L. Duchien, M. Huchard, R. Rabiser, C. Salinesi, C. Seidl, X. T¨ ernava, L. Teixeira, T. Th¨um, & T. Zadi (Eds.) 23rd intl. systems and software product line conference, SPLC Volume b, Paris, France, September 9-13, 2019 (p. 2019). ACM. Galindo, J., Benavides, D., Trinidad, P., Guti´ errez-Fern´ andez, A., & Ruiz-Cort´ es, A. (2019). Automated analysis of feature models Quo vadis? Computing,101(5), 387–433. Gent, I., Miguel, I., Nightingale, P., McCreesh, C., Prosser, P., Nooore, N., & Unsworth, C. (2018). A review of literature on parallel constraint solving. Theory and Practice of Logic Programming,18(5–6), 725– 758. Hamadi, Y., & Sais, L. (2018). Handbook of Parallel Constraint Reasoning. Berlin: Springer. Horcas, J., Pinto, M., & Fuentes, L. (2018). Variability models for generating efficient configurations of functional quality attributes. Information and Software Technology,95, 147–164. Jannach, D., Schmitz, T., & Shchekotykhin, K. (2015). Parallelized hitting set computation for model-based diagnosis. In 29th AAAI conference on artificial intelligence (pp. 1503–1510). Texas: AAAI Press. Jannach, D., Schmitz, T., & Shchekotykhin, K. (2016). Parallel Model-Based diagnosis on Multi-Core computers. Journal of Artificial Intelligence Research,55, 835–887. Junker, U. (2004). QUICKXPLAIN: Preferred Explanations and Relaxations for Over-constrained Problems. In 19th national conference on artifical intelligence (pp. 167–172 ). San Jose: AAAI Press. Kastner, C., Thum, T., Saake, G., Feigenspan, J., Leich, T., Wielgorz, F., & Apel, S. (2009). Featureide: A tool framework for feature-oriented software development. In 31St IEEE intl. conference on software engineering (pp. 611–614). IEEE. Le, V. M., Felfernig, A., Uta, M., Benavides, D., Galindo, J., & Tran, T.N.T. (2021). DirectDebug: Automated testing and debugging of feature models. In 43Rd IEEE/ACM intl. conference on software engineering: New ideas and emerging results (pp. 81–85). IEEE/ACM. Le Berre, D., & Parrain, A. (2010). The SAT4JLibrary, Release 2.2. Journal on Satisfiability. Boolean Modeling and Computation,7(2-3), 59–64. 507 Marques-Silva, J., Heras, F., Janota, M., Previti, A., & Belov, A. (2013). On computing minimal correction subsets. In 23Rd intl. joint conference on artificial intelligence. Beijing, China (pp. 615–622). O’Sullivan, B., Nanopulos, A., Faltings, B., & Pu, P. (2007). Representative explanations for Over- Constrained problems. In 22Nd AAAI conference on artificial intelligence (pp. 323–328). Canada: Vancouver. Reiter, R. (1987). A theory of diagnosis from first principles. Artificial Intelligence,23(1), 57–95. Ricci, F., Rokach, L., Shapira, B., & Kantor, P. (2011). Recommender Systems Handbook, Springer, Berlin. Rossi, F., Venable, K., & Walsh, T. (2011). A Short Introduction to Preferences: Between Artificial Intelligence and Social Choice. California: Morgan & Claypool Publishers. Schmitz, T., & Jannach, D. (2017). An AI-based interactive tool for spreadsheet debugging. In IEEE symposium on visual languages and human-centric computing (VL/HCC’17) (pp. 333–334). USA: IEEE. Stumptner, M. (1997). An Overview of Knowledge-based Configuration. Ai Communications,10(2), 111– 125. Thum, T., Batory, D., & Kastner, C. (2009). Reasoning about edits to feature models. In 31St IEEE intl. conference on software engineering (pp. 254–264). Piscataway: IEEE. Tran, T. N. T., Felfernig, A., & Tintarev, N. (2021). Humanized Recommender Systems: State-of-the-art and Research Issues. ACM Transactions on Interactive Intelligent Systems,11(2), 1–41. Tsang, E. (1993). Foundations of Constraint Satisfaction. Cambridge: Academic Press. Varela-Vaca, A., Galindo, J. A., Ramos-Guti´ errez, B., G´ omez-L´ opez, M., & Benavides, D. (2019). Process mining to unleash variability management: discovering configuration workflows using logs. In Proceedings of the 23rd intl. systems and software product line conference, (Vol. A pp. 265–276). Vecchio, M., Azzoni, P., Menychtas, A., Maglogiannis, I., & Felfernig, A. (2021). A fully open-source approach to intelligent edge computing: the AGILE’s lesson. Sensors,21(4), 1309. Vidal, C., Felfernig, A., Galindo, J., Atas, M., & Benavides, D. (2020). A Parallelized Variant of Junker’s QUICKXPLAIN Algorithm. In 25Th intl. symp. on methodologies for intell. Syst., volume 12117 of springer lecture notes in computer science (pp. 457–468). Springer. Walsh, T. (2007). Representing and reasoning with preferences. AI Magazine,28(4), 59–70. White, J., Benavides, D., Schmidt, D. C., Trinidad, P., Dougherty, B., & Ruiz-Cortes, A. (2010). Automated diagnosis of feature model configurations. J. Syst Softw.,83(7), 1094–1107. Wotawa, F. (2001). A variant of reiter’s Hitting-Set algorithm. Information Processing Letters,79(1), 45–51. Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 508