Knowledge-based Configuration: From Research to Business Cases, FIRST EDITION (2014)

Part II. Basics

Chapter 7. Conflict Detection and Diagnosis in Configuration

Alexander Felfernig^a, Stefan Reiterer^b, Florian Reinfrank^a, Gerald Ninaus^a and Michael Jeran^a, ^aGraz University of Technology, Graz, Austria, ^bSelectionArts, Graz, Austria

Abstract

The widespread industrial application of configuration technologies triggers an increasing demand for intelligent techniques that efficiently support anomaly management operations for configuration knowledge bases. Examples of such operations are the testing and debugging of faulty knowledge bases (see Chapter 11) and the detection of redundancies in configuration knowledge bases (see Chapter 12). The goal of this chapter is to discuss techniques and algorithms that form the technological basis for the aforementioned anomaly management operations.

Keywords

Knowledge-based Configuration; Conflict Detection; Diagnosis

Acknowledgments

The work presented in this chapter was funded by the Austrian research promotion agency (grant number: 827587).

7.1 Introduction

Anomalies can be characterized as parts of a knowledge base that conform to a defined pattern of unintended structures (see also Chandola et al., 2009). Anomaly management operations presented in this book are the automated testing and debugging of configuration knowledge bases (see Friedrich et al., 2014¹) and the automated detection of redundancies in configuration knowledge bases (see Felfernig et al., 2014²). Anomaly management operations are very important since configuration knowledge bases are often complex and subject to frequent changes (Barker et al., 1989; Fleischanderl et al., 1998).

The foundations for anomaly management are conflict detection and diagnosis algorithms that help to detect (1) minimal subsets of the knowledge base that are responsible for a faulty behavior (Felfernig et al., 2004, 2012, 2013; Junker, 2004) and (2) maximal subsets of the knowledge base that are redundancy-free (Felfernig et al., 2011). More precisely, conflict detection algorithms are able to determine minimal sets of constraints that are inconsistent; that is, do not allow the determination of a solution (configuration). In addition, diagnosis algorithms can determine minimal sets of constraints in the configuration knowledge base that have to be deleted or adapted such that the remaining set of constraints is consistent (see Friedrich et al., 2014); that is, a solution can be determined. Typically, diagnoses are determined from a given set of (minimal) conflicts and vice versa, minimal conflicts can be determined on the basis of a given set of (minimal) diagnoses (see Section 7.4).

The major focus of this chapter is to provide an introduction to some of the existing conflict detection and diagnosis techniques that are the foundation for the aforementioned anomaly management operations. The remainder of this chapter is organized as follows. In Section 7.2, we introduce the working example used in this chapter, a simplified version of the example configuration knowledge base introduced in Hotz et al. (2014).³ We discuss selected conflict detection algorithms in Section 7.3 and the corresponding diagnosis algorithms in Section 7.4. On the basis of the results of a performance analysis, we discuss the advantages and disadvantages of the presented conflict detection and diagnosis algorithms. Section 7.5 concludes this chapter.

7.2 Example

We introduce a working example that is based on the configuration knowledge base introduced in Hotz et al. (2014). For the following discussions we introduce the configuration knowledge base () of a fragment of a personal computer (PC), which consists of the component types MB (motherboard) and CPU (central processing unit) and their specific subtypes {MBSilver, MBDiamond} and {CPUS, CPUD}.

The following personal computer (PC) configuration knowledge base (configuration model) is inconsistent, meaning that it does not allow the calculation of a solution (configuration). Such situations often occur as a result of maintenance operations in a knowledge base where, for example, conflicts are introduced due to the insertion of new elements or due to the adaptation of existing ones. In our working example we assume that constraint (CPUS requires MBSilver) has been added by the knowledge engineer in order to replace the faulty constraint (CPUS requires MBDiamond). Unfortunately, the knowledge engineer inserted without deleting . Our example also assumes that a constraint (instances of the component type CPUD should not be part of any configuration) was introduced earlier for testing purpose with no intent to have it pertaining to the configuration model. However the knowledge engineer forgot to disable it after testing the model. Constraint states that an MBSilver must not be combined with a CPUD and constraint states that an MBDiamond must not be combined with a CPUS.

We will now start with a discussion of algorithms that focus on conflict detection and then show how to exploit identified minimal conflict sets in order to determine corresponding diagnoses. Note that conflict detection and diagnosis algorithms discussed hereafter are a basis for the concepts explained in Friedrich et al. (2014)⁴ and Felfernig et al. (2014).⁵

7.3 Determining Minimal Conflict Sets

Before discussing basic conflict detection algorithms useful for (but not limited to) configuration scenarios, we introduce the definition of a conflict (conflict set) in the context of an inconsistent configuration knowledge base.

Definition

Minimal Conflict Set

A conflict set is a subset of such that inconsistent (). represents the set of all constraints in the knowledge base (), represents the background knowledge (no conflict elements are assumed to be included in ), and represents the set of constraints subject of conflict search. A conflict set CS is minimal if there does not exist a that has the conflict property.

Note that if we want to analyze the whole knowledge base (taking into account the complete set of constraints in conflict set search), we simply have to define and, as a consequence, .

In our working example we are able to identify the following minimal conflict sets: and . These sets do not allow the determination of a solution; inconsistent () and inconsistent (). and are minimal since none of their subsets fulfills the conflict set property. Each minimal conflict set (conflict) can simply be resolved by deleting one of its elements. This approach is used by some of the diagnosis algorithms discussed in Section 7.4.

In the remainder of this section we introduce and evaluate two basic conflict detection algorithms: SIMPLECONFLICTDETECTION and QUICKXPLAIN.

7.3.1 Simple Conflict Detection

The first approach to the determination of minimal conflict sets is SIMPLECONFLICTDETECTION (see Algorithm 7.1). Conforming with the introduced definition of a conflict set, the algorithm focuses the search for a minimal conflict by explicitly specifying the set of constraints that might induce a conflict. Note that SIMPLECONFLICTDETECTION determines exactly one conflict set per computation. In order to identify all minimal conflicts in , this algorithm has to be combined with a HSDAG-based diagnosis algorithm (see Section 7.4).

The set CS collects all relevant elements (constraints) of the minimal conflict. If the deletion of all constraints of C does not allow the determination of a solution (inconsistent(B)) or ) itself is consistent, there is no need for searching for a conflict (the empty set is returned). In all other cases, the algorithm tries to identify a minimal conflict. In order to achieve this goal, elements of are extracted and used to figure out whether they are triggering a conflict. If such an element has been identified, it is stored in the set , which collects the set of elements contributing to the conflict.

Algorithm 7.1

SIMPLECONFLICTDETECTION

In order to demonstrate the functionality of SIMPLECONFLICTDETECTION, the basic steps of this algorithm are shown in Table 7.1. For this example (see also Figure 7.1) we take the constraints of our domain description (DD) and assume that and ). The inner loop is responsible for detecting individual elements that participate in the conflict, the outer loop is responsible for checking whether the generated set is already inconsistent (i.e., a minimal conflict set could be found).

Table 7.1

Example of the application of SIMPLECONFLICTDETECTION. is returned as minimal conflict set (CS) for and .

FIGURE 7.1 A conflict set CS is a subset of ), which is inconsistent with B. CS is minimal if no subset of CS fulfills the conflict set property. In this context, B is the background knowledge that includes all constraints considered correct. An example conflict set is .

Algorithm Analysis. If a minimal conflict set can be determined ( consistent and inconsistent), SIMPLECONFLICTDETECTION needs O(2) additional consistency checks in the best case (a constraint that represents a singleton conflict and is located at the first position of the constraint list ). In the worst case, each element of is also part of the minimal conflict—in this case, additional consistency checks are needed.

7.3.2 QuickXPlain

A more efficient approach to the determination of minimal conflict sets is QUICKXPLAIN introduced by (Junker, 2004; see Algorithm 7.27.2). This algorithm is based on the concept of divide and conquer: each time it detects that the first half of a constraint set is already inconsistent, the second half of the constraint set is omitted (not further taken into account when determining the conflict). This is an efficient way to get rid of constraints that do not participate in the conflict.

Algorithm 7.2

QUICKXPLAIN

QUICKXPLAIN determines exactly one conflict set per computation. In order to identify all minimal conflicts in , this algorithm has to be combined with a HSDAG-based diagnosis algorithm (see Section 7.4). How QUICKXPLAIN determines a minimal conflict can best be explained on the basis of our working example (see Table 7.2). The activation hierarchy for the recursive function QX is depicted in Figure 7.2.

Table 7.2

Example of QUICKXPLAIN: is the (original) background knowledge and is the returned conflict set. The sequence of the different QX activations is depicted in Figure 7.2.

FIGURE 7.2 Activation sequence of the different QUICKXPLAIN instances (for details see Table 7.2).

The function QX adds additional constraints (from ) to the background knowledge as long as the resulting constraint set remains consistent. If it becomes inconsistent, the algorithm leaves out the remaining constraints. For example, in Table 7.2 (step 5) the set is inconsistent and the remaining constraint can be left out. On the other hand, if the background knowledge is consistent and only one constraint remains that induces the inconsistency, this constraint must be part of the conflict set. For example, inTable 7.2 (step 4) the background knowledge consists of the constraints and remains as single constraint. It is clear that is part of the conflict since is consistent but is inconsistent.

Algorithm Analysis. When comparing the performance of SIMPLECONFLICTDETECTION with QUICKXPLAIN we can see that QUICKXPLAIN has the potential to reduce the number of needed consistency checks. In our working example, SIMPLECONFLICTDETECTION needs 11 consistency checks whereas QUICKXPLAIN only needs eight consistency checks. In the worst case, the algorithm needs where is the set size of the minimal conflict and is the number of constraints in (Junker, 2004). The best case complexity with regard to the number of consistency checks is .

Note that both of the presented conflict detection algorithms determine conflicts depending on the constraint ordering. If we reverse the ordering of the constraints of both algorithms, we would receive the conflict set first. For a more detailed discussion of issues related to constraint orderings and their role in conflict detection refer to Junker (2004).

7.3.3 Runtime Performance of Conflict Detection Algorithms

We conclude our discussion of conflict detection issues with an analysis of the runtime performance of the presented algorithms when executed on real-world configuration datasets taken from www.splot-research.org. The average runtime of the two algorithms was measured in milliseconds (ms) where in each setting the ordering of the constraints was randomized and each setting was executed 100 times. It becomes clear that QUICKXPLAIN clearly outperforms SIMPLECONFLICTDETECTION in all of the analyzed settings (seeTable 7.3).

Table 7.3

Runtime evaluation: The average runtime in milliseconds (ms) needed by SIMPLECONFLICTDETECTION (SCD) and QUICKXPLAIN to calculate one minimal conflict set (on a standard PC). The basis for this evaluation are knowledge bases from www.splot-research.org.

A major influence factor for the performance of QUICKXPLAIN is the size of conflict sets—the more elements in the conflicts, the more consistency checks are needed for determining one minimal conflict set. Another factor that has an impact on the performance of QUICKXPLAIN is ordering of the constraints in the consideration set . The more these constraints are spread over the more consistency checks can be expected since less constraints can be omitted in early phases of QX execution.

7.4 Determining Minimal Diagnoses

Conflict sets help to identify areas of inconsistencies within a set of constraints. If we want to know the minimal set of constraints that have to be adapted (or deleted from the configuration knowledge base) such that a solution can be found for the given configuration task, we need to determine the (minimal) diagnoses with regard to the determined conflict sets. Based on our definition of a conflict set in Section 7.3, we now introduce the definition of a diagnosis task and the corresponding diagnosis (solution).

Definition

Diagnosis Task

A diagnosis task can be defined by the tuple () where is the background knowledge, and is the set of constraints to be analyzed.

Before discussing potential algorithms that support the calculation of minimal diagnoses, we introduce the definition of a diagnosis that represents a solution to a given diagnosis task . The basic idea of diagnosis determination is depicted in Figure 7.3.

Definition

Diagnosis

A diagnosis for a given diagnosis task (C,AC) is a set of constraints such that is consistent. A diagnosis is minimal if there does not exist a diagnosis with the diagnosis property. Finally, a minimal diagnosis is denoted asminimal cardinality diagnosis if there does not exist a minimal diagnosis with .

FIGURE 7.3 A diagnosis is a subset of ) such that is consistent. is minimal if no subset of fulfills the diagnosis property. B again represents the background knowledge. An example diagnosis is .

A widespread approach to the determination of diagnoses (hitting sets) is the construction of a HSDAG. The algorithm is known as hitting set directed acyclic graph algorithm, which has been introduced by Reiter (1987).

7.4.1 Hitting Set Directed Acyclic Graph (HSDAG)

The HSDAG algorithm supports the determination of minimal diagnoses. Since the algorithm performs diagnosis search typically in breadth-first fashion, it supports the determination of minimal cardinality diagnoses (i.e., minimal diagnoses with the lowest possible number of included constraints). However, the algorithm is complete; after returning minimal cardinality diagnoses, it returns all other diagnoses contained in the consideration set . HSDAG structures can be established by repeatedly activating a conflict detection algorithm (e.g., SIMPLECONFLICTDETECTION or QUICKXPLAIN) and to analyze the different possibilities to resolve the returned conflict. Since this is a simple implementation of a breadth-first search strategy, we do not provide an algorithm here.

For example, in Figure 7.4 the first minimal conflict set returned by the conflict detection algorithm is . If we resolve the conflict , by deleting the constraint , another conflict set will be identified – .

FIGURE 7.4 Breadth-first based search for diagnoses on the basis of the minimal conflict sets and . The resulting minimal diagnoses are , and .

Due to the minimality of we have exactly three different alternatives to resolve the conflict (by deleting one of its elements). The HSDAG algorithm is complete—all different alternatives to resolve the given conflicts are analyzed. For example, if we delete from , we have already determined our first diagnosis, . The second minimal cardinality diagnosis that can be derived from the HSDAG is . There is a third minimal diagnosis (which is not a minimal cardinality one): .

The HSDAG algorithm (Reiter, 1987) not only supports the determination of hitting sets in terms of diagnoses—given a predefined set of diagnoses we are also able to derive all corresponding minimal conflicts (see, e.g., Figure 7.5). Typical HSDAG implementations are based on a number of additional concepts that help to improve the performance of diagnosis (conflict set) detection. First, conflicts (diagnoses) can be reused in the sense that already determined conflicts (diagnoses) can be reused for those paths of the HSDAG which do not include the corresponding elements. In our working example (see Figure 7.5) there is no possibility to reuse a conflict set due to the fact that there is only one path to the leaf node of the HSDAG.

FIGURE 7.5 Breadth-first based search for conflicts on the basis of the minimal diagnoses , and . The resulting minimal conflict sets are .

A second possibility to improve the performance of diagnosis search is to close specific paths in the tree that have already been expanded in other parts of the tree. In our working example (see Figure 7.3), the path directly leads to a diagnosis. For this reason it does not make sense to further expand other paths that include . We can also take into account situations where two paths contain the same set of elements. In such a situation, one of these paths can be closed (i.e., does not have to be expanded further).

7.4.2 FastDiag

There are many situations where not all the existing diagnoses are of relevance to the user. For example, when interacting with a configurator, the user is not interested in having to handle a possibly huge number of alternative diagnoses. There is a need for algorithms that are able to determine so-called leading diagnoses quickly, which can then be analyzed and evaluated by the user. Since in many cases not all possible diagnoses can be determined (for performance reasons), diagnoses assumed to be relevant for the user are determined first—these diagnoses are denoted as leading diagnoses. FASTDIAG is an algorithm that efficiently determines leading diagnoses without the additional overhead of determining conflict sets. It is easy to implement (no conflict detection and HSDAG algorithm are needed for determining one diagnosis) and is specifically useful in interactive configuration settings, for example, to support the user in situations where no solution can be found (Felfernig et al., 2012).

In the line of QUICKXPLAIN, FASTDIAG heavily relies on the concept of divide and conquer. Assuming that the set is inconsistent, the major idea is to divide the set of constraints into two different subsets and . If, for example, is consistent, we already know that the set includes a diagnosis and, as a consequence, there is no need to further analyze with regard to further diagnosis elements. A major advantage of FASTDIAG is that it is based on conflict-independent search strategies (i.e., no conflicts are needed for determining a diagnosis). FASTDIAG determines exactly one diagnosis at a time (if one exists). If we are interested in all diagnoses for a given set of constraints , we have to combine FASTDIAG with a corresponding HSDAG algorithm (see the example inFigure 7.5).

How FASTDIAG determines minimal diagnoses can best be explained using our working example (see Table 7.4). The activation hierarchy for the FASTDIAG function is depicted in Figure 7.6. The algorithm checks whether the deletion of constraints (from ) makes the remaining constraints consistent. For example, if we delete from in step 1 (Table 7.4) we are able to restore the consistency. At the same time we also know that there must be a diagnosis in since its deletion from contributed to the restoration of consistency. Furthermore, there is no need to search for a diagnosis in .

Table 7.4

Example of FASTDIAG: is the (original) background knowledge and is the returned diagnosis. The activation sequence of the different FASTDIAG instances is depicted in Figure 7.6.

FIGURE 7.6 Activation sequence of the different FASTDIAG instances (for the details see Table 7.4).

Algorithm Analysis. When comparing the performance of HSDAG with FASTDIAG we can see that FASTDIAG has the potential the reduce the number of needed consistency checks especially in scenarios where there is a need for identifying so-called leading diagnoses (i.e., not the complete set of diagnoses). In the worst case, FASTDIAG needs where is the set size of the minimal diagnosis and is the number of constraints in (Junker, 2004). The best case complexity with regard to the number of consistency checks is .

The efficiency of FASTDIAG can best be documented by the fact that the number of consistency checks needed for determining one diagnosis is similar to the number of consistency checks needed by QUICKXPLAIN to determine exactly one conflict set. Typically, there is more than one conflict set in an inconsistent configuration knowledge base. Let be the number of minimal conflict sets in a constraint set and be the number of minimal diagnoses, then we need exactly calls of the function (see Algorithm 7.3) plus additional consistency checks and activations of QUICKXPLAIN with additional consistency checks for determining all diagnoses. The results of a performance evaluation (comparison of the HSDAG-based approach with FASTDIAG) are depicted inTable 7.5.

Algorithm 7.3

FASTDIAG

Table 7.5

Runtime evaluation: The average runtime in milliseconds (ms) needed by HSDAG and FASTDIAG to calculate one minimal diagnosis (on a standard PC). The basis for this evaluation are knowledge bases from www.splot-research.org (Dell laptops (laptops), smarthomes (homes), cars, and Xerox printers (printers)).

7.4.3 Further Approaches

We now sketch two further approaches than can be used for the determination of diagnoses. First, we show how to represent the task of identifying minimal cardinality diagnoses as an optimization problem. This approach is based on the assumption that all minimal conflicts have been determined before the start of the diagnosis process (see, e.g., Fijany and Vatan, 2004). Second, we show how to determine minimal cardinality diagnoses in the simple case that the complete set of possible configurations is available—in this case, all diagnoses are known beforehand and the task is to identify the minimal ones (see, e.g., Jannach, 2008; Schubert and Felfernig, 2011; Schubert et al., 2010).

Diagnosis as Optimization Problem. We explain the approach to represent a diagnosis task as an optimization problem on the basis of the example depicted in Table 7.6. Each minimal conflict set is represented by a tuple that describes for each constraint whether it is part of the conflict set or not ( is part of the conflict set, is not part of the conflict set).

Table 7.6

Representation of a diagnosis task as optimization problem. In this case, all minimal conflict sets () have to be determined before the optimization can start (1 (0) denotes the fact that is part (not part) of the minimal conflict set).

On the basis of this information we are able to define a corresponding optimization problem. Each constraint of Table 7.6 is represented by a corresponding variable with dom()={0,1}. The conflict sets are represented in the form of constaints , for example, requires that at least one constraint out of has to be deactivated; that is, denotes the fact that constraint is inactive (which also means that the corresponding conflict has been resolved). The complete set of constraints that corresponds to the conflict sets in Table 7.6 is the following.

To complete the definition of the optimization problem, we introduce an optimization criterion. This criterion (see Formula 7.1) expresses the fact that the number of constraints that are part of at least one minimal conflict set and that are deactivated should be minimized. For further details on optimization-based diagnosis refer to Fijany and Vatan (2004).

(7.1)

Filtering Minimal Cardinality Diagnoses. We explain the approach to determine minimal cardinality diagnoses in the case that all possible configurations are already available (see Tables 7.7 and 7.8). Table 7.7 depicts the definition of a configuration task defined by a set of variables (), their domains , and a constraint that describes the set of possible configurations ().

Table 7.7

A simple configuration problem defined by the variables , = {1,2,3}, and the constraint .

Table 7.8

Example user requirements and their relationship to the configurations (1 = requirement supported, 0 = not supported).

On the basis of the information contained in Table 7.7 we are able to derive an intermediate representation that indicates for each user (customer) requirement ()⁶ and each configuration () whether the requirement is supported by or not (see Table 7.8). The support value indicates how many of the user requirements are supported by the configuration; for example, configuration supports the user requirement but not the remaining ones; consequently the support of . It should be clear now that we are interested in diagnoses for the given set of requirements—the minimal (cardinality) set of requirements that have to be deleted such that a solution can be identified.

On the basis of the intermediate representation (see Table 7.8) it is straightforward to determine, for example, one minimal cardinality diagnosis. The configuration with the maximum support also defines a minimal cardinality diagnosis since there does not exist a diagnosis with (if this would be the case then would not have the maximum support value). In our working example, the only minimal cardinality diagnosis is .

7.5 Conclusion

In this chapter, we sketched major concepts, techniques, and algorithms that support anomaly management in constraint-based application development, especially configurator application development. These concepts are the basis for other chapters in this book (see Friedrich et al., 2014⁷ and Felfernig et al., 2014⁸).

References

1. Barker V, O’Connor D, Bachant J, Soloway E. Expert systems for configuration at Digital: XCON and beyond. Communications of the ACM. 1989;32(3):298–318.

2. Chandola V, Banerjee A, Kumar V. Anomaly Detection: A Survey. ACM Computing Surveys. 2009;41(3):1–58.

3. Felfernig A, Friedrich G, Jannach D, Stumptner M. Consistency-based diagnosis of configuration knowledge bases. Artificial Intelligence. 2004;152(2):213–234.

4. Felfernig A, Zehentner C, Blazek P. CoreDiag: eliminating redundancy in constraint sets. In: 22nd International Workshop on Principles of Diagnosis (DX’2011), Murnau, Germany. 2011;219–224.

5. Felfernig A, Schubert M, Zehentner C. An efficient diagnosis algorithm for inconsistent constraint sets. Artificial Intelligence for Engineering Design, Analysis and Manufacturing (AI EDAM). 2012;26(1):53–62.

6. Felfernig A, Schippel S, Leitner G, et al. Automated repair of scoring rules in constraint-based recommender systems. AI Communications. 2013;26(2):15–27.

7. Felfernig A, Reinfrank F, Ninaus G, Blazek P. Redundancy detection in configuration knowledge. In: Felfernig A, Hotz L, Bagley C, Tiihonen J, eds. Knowledge-based Configuration – From Research to Business Cases. Waltham, MA: Morgan Kaufmann Publishers; 2014:157–166. (Chapter 12).

8. Fijany A, Vatan F. New approaches for efficient solution of hitting set problem. In: Winter International Symposium on Information and Communication Technologies. Cancun, Mexico: Trinity College Dublin; 2004:1–6.

9. Fleischanderl G, Friedrich GE, Haselböck A, Schreiner H, Stumptner M. Configuring large systems using generative constraint satisfaction. IEEE Intelligent Systems. 1998;13(4):59–68.

10. Friedrich G, Jannach D, Stumptner M, Zanker M. Knowledge engineering for configuration systems. In: Felfernig A, Hotz L, Bagley C, Tiihonen J, eds. Knowledge-based Configuration – From Research to Business Cases. Waltham, MA: Morgan Kaufmann Publishers; 2014:139–155. (Chapter 11).

11. Hotz L, Felfernig A, Stumptner M, Ryabokon A, Bagley C, Wolter K. Configuration knowledge representation and reasoning. In: Felfernig A, Hotz L, Bagley C, Tiihonen J, eds. Knowledge-based Configuration – From Research to Business Cases. Waltham, MA: Morgan Kaufmann Publishers; 2014:41–72. (Chapter 6).

12. Jannach D. Finding preferred query relaxations in content-based recommenders. In: London, UK: Studies in Computational Intelligence; 2008:81–97. Chountas P, Petrounias I, Kacprzyk J, eds. Intelligent Techniques and Tools for Novel System Architectures. vol. 109.

13. Junker U. QUICKXPLAIN: preferred explanations and relaxations for over-constrained problems. In: McGuinness DL, Ferguson G, eds. 19th International Conference on Artifical Intelligence (AAAI’04). San Jose, CA: AAAI Press; 2004:167–172.

14. Reiter R. A theory of diagnosis from first principles. Artificial Intelligence. 1987;32(1):57–95.

15. Schubert M, Felfernig A. BFX: diagnosing conflicting requirements in constraint-based recommendation. International Journal on Artificial Intelligence Tools. 2011;20(2):297–312.

16. Schubert M, Felfernig A, Mandl M. FastXPlain: conflict detection for constraint-based recommendation problems. In: García-Pedrajas N, Herrera F, Fyfe C, Benítez J, Ali M, eds. Trends in Applied Intelligent Systems (Proceedings of 23rd International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2010). Cordoba, Spain: Springer; 2010;621–630. Lecture Notes in Computer Science vol. 6096.