An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets
This work addresses the need for efficient diagnosis in constraint-based systems, which is incremental as it builds on existing methods like hitting sets.
The paper tackles the problem of identifying minimal sets of faulty constraints in over-constrained systems, such as in configuration sessions or knowledge base engineering, and introduces the FastDiag algorithm, which shows performance advantages over conflict-directed hitting set methods in efficiency analysis.
Constraint sets can become inconsistent in different contexts. For example, during a configuration session the set of customer requirements can become inconsistent with the configuration knowledge base. Another example is the engineering phase of a configuration knowledge base where the underlying constraints can become inconsistent with a set of test cases. In such situations we are in the need of techniques that support the identification of minimal sets of faulty constraints that have to be deleted in order to restore consistency. In this paper we introduce a divide-and-conquer based diagnosis algorithm (FastDiag) which identifies minimal sets of faulty constraints in an over-constrained problem. This algorithm is specifically applicable in scenarios where the efficient identification of leading (preferred) diagnoses is crucial. We compare the performance of FastDiag with the conflict-directed calculation of hitting sets and present an in-depth performance analysis that shows the advantages of our approach.