Source-linked AI summary
An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets
Alexander Felfernig, Monika Schubert, Christoph Zehentner
TL;DR
Inconsistent constraint sets require minimal deletions to restore consistency, especially during configuration and knowledge-base engineering. The paper introduces FASTDIAG, a divide-and-conquer direct diagnosis algorithm, and reports efficient preferred-diagnosis calculation compared with HSDAG approaches.
Problem
Constraint sets can become inconsistent with test cases or customer requirements, creating a need to identify minimal constraints for deletion to restore consistency.
Method
FASTDIAG uses divide-and-conquer direct diagnosis to determine one preferred minimal diagnosis at a time without calculating conflict sets.
Results
FASTDIAG outperforms breadth-first and best-first HSDAG for calculating one and the topmost-5 minimal diagnoses, while achieving RMSD 0.95.
Takeaways & Limitations
FASTDIAG is especially applicable when preferred diagnoses are needed or when the number of conflict sets is at least the number of diagnoses.
Takeaways & Limitations
Calculating all minimal diagnoses remains expensive for interactive settings, motivating reduced subsets of preferred diagnoses.
Abstract
from arXiv · showhide
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.
1 Introduction
Constraint technologies support configuration, recommendation, and scheduling, but their constraint sets can become over-constrained. The paper introduces FASTDIAG to efficiently identify preferred minimal diagnoses without relying on conflict-set calculation.
- Constraint technologies are applied in configuration, recommendation, and scheduling.
- Over-constrained sets arise when configuration knowledge bases conflict with test cases or customer requirements.
- Standard diagnosis approaches combine conflict detection with hitting-set algorithms to identify minimal faulty constraint sets.
- FASTDIAG directly determines one minimal diagnosis at a time with the same computational effort as determining one conflict set.
- FASTDIAG supports preferred diagnoses in online configuration, recommendation, SAT solving, and description-logics reasoning.
2 Example Domain: Car Configuration
The paper uses automotive configuration as a working example, formalizing it as a CSP with variables, finite domains, knowledge-base constraints, and customer requirements. Configurations must satisfy consistency and completeness to be valid.
- A configuration task is modeled as a CSP consisting of finite-domain variables, their domains, and combined knowledge-base and customer constraints.
- The automotive example uses variables for car type, parking distance control, fuel, ski storage, and four-wheel drive.
- The example separates four configuration-knowledge-base constraints from three customer requirements.
- A configuration is an instantiation assigning each variable a value from its domain.
- A valid configuration is both consistent with the constraints and complete over all variables.
3 Diagnosing Over-Constrained Problems
Diagnosis removes minimal customer-requirement subsets so the remaining constraints become consistent. The standard HSDAG approach resolves minimal conflicts, but enumerating all diagnoses is expensive for interactive use, motivating preferred-diagnosis methods such as FASTDIAG.
- A minimal diagnosis is a minimal subset of customer requirements whose deletion restores consistency with the configuration knowledge base.
- A conflict set is a customer-requirement subset inconsistent with the knowledge base, and it is minimal when no proper subset is also conflicting.
- The example contains three minimal conflicts: CS1={c5,c6}, CS2={c5,c7}, and CS3={c6,c7}.
- HSDAG resolves all minimal conflict sets through a hitting-set directed acyclic graph to identify minimal diagnoses.
- Breadth-first HSDAG enumerates diagnoses such as ∆1={c5,c6}, ∆2={c5,c7}, and ∆3={c6,c7}.
- Enumerating all diagnoses is expensive for interactive settings, while FASTDIAG seeks preferred diagnoses without calculating conflict sets.
4 Calculating Preferred Diagnoses with FASTDIAG
FASTDIAG identifies preferred minimal diagnoses by recursively dividing the constraint set and using consistency checks to eliminate subsets. Repeated runs can enumerate multiple diagnoses, while preference ordering constrains diagnoses along individual search paths but only partially orders the full search tree.
- Preferred Diagnoses: Preferred diagnoses are minimal diagnoses selected using a total lexicographical ordering over constraints, beginning with the least important constraints.The ordering determines which constraints are preferred for deletion when multiple minimal diagnoses exist.
- FASTDIAG Approach: FASTDIAG starts with AC as the union of customer requirements and the configuration knowledge base, then applies divide-and-conquer diagnosis search.The recursive FD procedure splits the current constraint set into C1 and C2 and checks whether one subset already contains a diagnosis.
- Calculating n>1 Diagnoses: In the working example, FASTDIAG first derives ∆={c5, c6} and then checks reduced customer-requirement sets to identify additional minimal diagnoses.Deleting an element from a previously found diagnosis and rerunning FASTDIAG yields further diagnoses, following the adapted HSDAG construction.
- Calculating n>1 Diagnoses: Diagnoses on one search-tree path follow a strict preference ordering, but a diagnosis at level k is not necessarily preferable to one at level k+1.The paper therefore characterizes the resulting ordering across the search tree as partial.
- FASTDIAG Approach: When a subset already contains a diagnosis, FASTDIAG omits the other subset; singleton inconsistent cases identify the remaining constraint as part of a minimal diagnosis.The algorithm returns the union of diagnoses found through its recursive branches.
- FASTDIAG Properties: FASTDIAG computes only minimal diagnoses because its recursive deletion and singleton conditions prevent returning diagnoses with removable constraints.The paper gives separate arguments for completeness with respect to identifiable minimal diagnoses and for excluding non-minimal diagnoses.
5 Evaluation
The evaluation compares FASTDIAG with hitting-set diagnosis using QUICKXPLAIN and examines computational complexity, runtime, consistency-check effort, and diagnosis-prediction quality. FASTDIAG outperforms the HSDAG variants for first and topmost-5 diagnoses, while achieving the lowest RMSD and strong precision.
- Performance comparison: FASTDIAG is compared with hitting-set diagnosis combined with QUICKXPLAIN for computational performance.The evaluation considers runtime and the number of consistency or TP calls across configuration problems.
- Complexity: The worst-case consistency-check complexity for one FASTDIAG diagnosis is 2d·log2(n^d)+2d, while the best case is log2(n^d)+2d.Here, d is the minimal diagnosis-set size and n is the number of constraints.
- Complexity: FASTDIAG and QUICKXPLAIN require logarithmic numbers of consistency checks per diagnosis or conflict set, respectively.FASTDIAG’s branching and leaf-check behavior differs between best and worst cases, but both approaches fall into a logarithmic complexity class per computed object.
- Performance comparison: FASTDIAG clearly outperforms breadth-first and best-first HSDAG when calculating either the first or the topmost-5 minimal diagnoses.Figures 4 and 5 report performance in milliseconds and the number of needed TP calls for 5, 7, 10, and 15 user requirements.
- Prediction quality: FASTDIAG achieved the lowest RMSD at 0.95, compared with 0.97 for best-first HSDAG and 1.64 for breadth-first HSDAG.RMSD measures the distance between the predicted and expected position of a diagnosis leading to the user-selected configuration.
- Prediction quality: FASTDIAG and best-first HSDAG had the highest precision, whereas breadth-first HSDAG had the worst precision.Precision measures how often a diagnosis leading to the selected configuration appears among the topmost-n predicted diagnoses.
6 Related Work
Related approaches improve diagnosis search by constructing conflict-set hitting sets, while FASTDIAG directly computes minimal diagnoses through divide-and-conquer. The comparison centers on efficiency, preferred diagnoses, and completeness guarantees.
- Conflict-directed diagnosis: Hitting-set diagnosis approaches typically rely on minimal conflict sets generated by QUICKXPLAIN.QUICKXPLAIN uses divide-and-conquer to calculate minimal conflict sets under a linear preference ordering.
- Direct diagnosis: FASTDIAG applies divide-and-conquer directly to determine one minimal diagnosis at a time, without requiring conflict sets.Its computational effort for one diagnosis corresponds to that required to determine one conflict set.
- Performance evaluation: FASTDIAG is evaluated against hitting-set diagnosis based on QUICKXPLAIN for topmost-10 and all minimal diagnoses across 5, 7, 10, and 15 requirements.The figures report performance in milliseconds and the number of needed TP calls.
- Guarantees: FASTDIAG provides completeness and diagnosis minimality, unlike stochastic approaches that improve search performance without general guarantees of either property.For more than one diagnosis, FASTDIAG can also exploit algorithms that optimize hitting-set determination.
- Personalized diagnosis: Existing approaches often overlook personalizing diagnoses to user preferences, although users may prefer diagnoses matching current preferences over minimum-cardinality diagnoses.Related work addresses personalization using similarity measures, probability estimates, and preference relations.
7 Conclusion
The conclusion presents FASTDIAG as an efficient direct diagnosis algorithm with logarithmic consistency-check complexity. It emphasizes applicability to preferred diagnoses and identifies repair actions, anytime diagnosis, and broader empirical evaluation as future work.
- Conclusion: FASTDIAG calculates one minimal diagnosis at a time with logarithmic complexity in the number of consistency checks.For one diagnosis, its computational complexity equals that of calculating one minimal conflict set in hitting-set approaches.
- Applicability: FASTDIAG is especially applicable when the number of conflict sets is at least the number of diagnoses or when preferred diagnoses are required.This scope directly targets settings where leading diagnoses matter.
- Future work: Future work includes determining repair actions, extending FASTDIAG to anytime diagnosis tasks, and conducting empirical studies in additional configurator domains.These directions concern both algorithmic extensions and broader evaluation.