A Diagnosis Algorithm for Inconsistent Constraint Sets



Alexander Felfernig Monika Schubert


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 constraints that have to be adapted or 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.

How to Cite

Felfernig , A. ., & Schubert , M. . (2010). A Diagnosis Algorithm for Inconsistent Constraint Sets. Annual Conference of the PHM Society, 2(2). https://doi.org/10.36001/phmconf.2010.v2i1.1948
Abstract 94 | PDF Downloads 107



Model-based diagnosis, Configuration, Constraint Satisfaction

(Ardissono et al., 2003) L. Ardissono, A. Felfernig, G. Friedrich, D. Jannach, G. Petrone, R. Schfer, and M. Zanker. A Framework for the development of personalized, distributed web-based configuration systems. AI Magazine, 24(3):93–108, 2003.

(Belanger, 2005) F. Belanger. A conjoint analysis of online consumer satisfaction. Journal of Electronic Commerce Research, 6:95–111, 2005.

(Castillo et al., 2005) L. Castillo, D. Borrajo, and M. Salido. Planning, Scheduling and Constraint Satisfaction: From Theory to Practice. IOS Press, 2005.

(Chen and Suen, 2003) Z. Chen and C. Suen. Measuring the complexity of rule-based expert systems. Expert Systems with Applications, 7(4):467–481, 2003.

(DeKleer et al., 1992) J. DeKleer, A. Mackworth, and R. Reiter. Characterizing diagnoses and systems. AI Journal, 56(2–3):197–222, 1992.

(DeKleer, 1990) J. DeKleer. Using crude probability estimates to guide diagnosis. AI Journal, 45(3):381–391, 1990.

(Felfernig et al., 2004) A. Felfernig, G. Friedrich, D. Jannach, and M. Stumptner. Consistency-based diagnosis of configuration knowledge bases. AI Journal, 152(2):213–234, 2004.

(Felfernig et al., 2007) A. Felfernig, G. Friedrich, K. Isak, K. Shchekotykhin, E. Teppan, and D. Jannach. Automated debugging of recommender user interface descriptions. Journal of Applied Intelligence, 31(1):1–14, 2007.

(Felfernig et al., 2008) A. Felfernig, G. Friedrich, E. Teppan, and K. Isak. Intelligent debugging and repair of utility constraint sets in knowledge-based recommender applications. In 13th ACM International Conference on Intelligent User Interfaces (IUI’08), pages 218–226, 2008.

(Felfernig et al., 2009) A. Felfernig, G. Friedrich, M. Schubert, M. Mandl, M. Mairitsch, and E. Tep- pan. Plausible repairs for inconsistent requirements. In 21st International Joint Conference on Artificial Intelligence (IJCAI’09), pages 791–796, 2009.

(Fleischanderl et al., 1998) G. Fleischanderl, G. Friedrich, A. Haselboeck, H. Schreiner, and M. Stumptner. Configuring large systems using generative constraint satisfaction. IEEE Intelligent Systems, 13(4):59–68, 1998.

(Friedrich and Shchekotykhin, 2005) G. Friedrich and K. Shchekotykhin. A general diagnosis method for ontologies. In 4th International Semantic Web Conference (ISWC’05), pages 232–246, 2005.

(Junker, 2004) U. Junker. Quickxplain: Preferred explanations and relaxations for over-constrained problems. In 19th National Conference on Artifi- cial Intelligence (AAAI’04), pages 167–172, 2004.

(Marques-Silva and Sakallah, 1996) J. Marques-Silva and K. Sakallah. Grasp: A new search algorithm for satisfiability. In International Conference on Computer-Aided Design, pages 220–227, 1996.

(Mittal and Frayman, 1989) S. Mittal and F. Frayman. Towards a generic model of configuration tasks. In 11th International Joint Conference on Artificial Intelligence (IJCAI’89), pages 1395–1401, 1989.

(O’Sullivan et al., 2007) Barry O’Sullivan, A. Papdopoulos, B. Faltings, and P. Pu. Representative explanations for over-constrained problems. In 22nd National Conference on Artificial Intelligence (AAAI’07), pages 323–328, 2007.

(Reiter, 1987) R. Reiter. A theory of diagnosis from first principles. AI Journal, 23(1):57–95, 1987.

(Sinz and Haag, 2007) C. Sinz and A. Haag. Con- figuration. IEEE Intelligent Systems, 22(1):78–90, 2007.

(Tsang, 1993) E. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.

(Winterfeldt and Edwards, 1986) D. Winterfeldt and W. Edwards. Decision analysis and behavioral research. Cambridge University Press, 1986.
Technical Research Papers