An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets
  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.
