# An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets

arXiv: https://arxiv.org/abs/2102.09005 · HTML: https://mlsanity.com/paper/2102.09005/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 38 references that are in the map.
- First posted on arXiv 17 Feb 2021.

## Built on by (most cited first, 11 of 11)

- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [AI Techniques for Software Requirements Prioritization](https://mlsanity.com/paper/2108.00832/) (2021)
- [How should I compute my candidates? A taxonomy and classification of diagnosis computation algorithms](https://mlsanity.com/paper/2207.12583/) (2022)
- [Anytime Diagnosis for Reconfiguration](https://mlsanity.com/paper/2102.09880/) (2021)
- [Configuring Multiple Instances with Multi-Configuration](https://mlsanity.com/paper/2109.09696/) (2021)
- [FastDiagP: An Algorithm for Parallelized Direct Diagnosis](https://mlsanity.com/paper/2305.06951/) (2023)
- [CoreDiag: Eliminating Redundancy in Constraint Sets](https://mlsanity.com/paper/2102.12151/) (2021)
- [An Overview of Direct Diagnosis and Repair Techniques in the WeeVis Recommendation Environment](https://mlsanity.com/paper/2102.12327/) (2021)
- [Designing Explanations for Group Recommender Systems](https://mlsanity.com/paper/2102.12413/) (2021)
- [Group Recommendation Techniques for Feature Modeling and Configuration](https://mlsanity.com/paper/2104.06054/) (2021)
- [Conjunctive Query Based Constraint Solving For Feature Model Configuration](https://mlsanity.com/paper/2304.13422/) (2023)

## Abstract (arXiv)

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.