{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T16:22:17Z","timestamp":1778343737854,"version":"3.51.4"},"reference-count":29,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2011,6,10]],"date-time":"2011-06-10T00:00:00Z","timestamp":1307664000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AIEDAM"],"published-print":{"date-parts":[[2012,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 (F<jats:sc>ast<\/jats:sc>D<jats:sc>iag<\/jats:sc>) that identifies minimal sets of faulty constraints in an overconstrained problem. This algorithm is specifically applicable in scenarios where the efficient identification of leading (preferred) diagnoses is crucial. We compare the performance of F<jats:sc>ast<\/jats:sc>D<jats:sc>iag<\/jats:sc> with the conflict-directed calculation of hitting sets and present an in-depth performance analysis that shows the advantages of our approach.<\/jats:p>","DOI":"10.1017\/s0890060411000011","type":"journal-article","created":{"date-parts":[[2011,6,10]],"date-time":"2011-06-10T10:27:14Z","timestamp":1307701634000},"page":"53-62","source":"Crossref","is-referenced-by-count":88,"title":["An efficient diagnosis algorithm for inconsistent constraint sets"],"prefix":"10.1017","volume":"26","author":[{"given":"A.","family":"Felfernig","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Schubert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Zehentner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2011,6,10]]},"reference":[{"key":"S0890060411000011_ref16","unstructured":"Fr\u00f6hlich P. , Nejdl W. , & Schroeder M. (1994). A formal semantics for preferences and strategies in model-based diagnosis. Proc. 5th Int. Workshop on Principles of Diagnosis (DX-94), pp. 106\u2013113."},{"key":"S0890060411000011_ref8","unstructured":"Feldman A. , Provan G. , & Gemund A. (2008). Computing minimal diagnoses by greedy stochastic search. Proc. 23rd AAAI Conf. Artificial Intelligence (AAAI\u201908), pp. 911\u2013918, Chicago."},{"key":"S0890060411000011_ref18","unstructured":"Junker U. (2004). QuickXplain: preferred explanations and relaxations for over-constrained problems. Proc. 19th National Conf. Artificial Intelligence (AAAI\u201904), pp. 167\u2013172, San Jose, CA."},{"key":"S0890060411000011_ref10","first-page":"213","article-title":"Consistency-based diagnosis of configuration knowledge bases","volume":"152","author":"Felfernig","year":"2004","journal-title":"AI Journal"},{"key":"S0890060411000011_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0957-4174(94)90072-8"},{"key":"S0890060411000011_ref25","unstructured":"Siddiqi S. , & Huang J. (2007). Hierarchical diagnosis of multiple faults. Proc. 20th Int. Joint Conf. Artificial Intelligence (IJCAI\u201907), pp. 581\u2013586, Hyderabad, India."},{"key":"S0890060411000011_ref17","doi-asserted-by":"crossref","unstructured":"Jannach D. , & Liegl J. (2006). Conflict-directed relaxation of constraints in content-based recommender systems. Proc. IEA\/AIE 2006, pp. 819\u2013829, Annency, France.","DOI":"10.1007\/11779568_88"},{"key":"S0890060411000011_ref2","first-page":"95","article-title":"A conjoint analysis of online consumer satisfaction","volume":"6","author":"Belanger","year":"2005","journal-title":"Journal of Electronic Commerce Research"},{"key":"S0890060411000011_ref28","volume-title":"Decision Analysis and Behavioral Research","author":"Winterfeldt","year":"1986"},{"key":"S0890060411000011_ref12","doi-asserted-by":"publisher","DOI":"10.1145\/1378773.1378802"},{"key":"S0890060411000011_ref15","first-page":"232","volume-title":"Proc. 4th Int. Semantic Web Conference (ISWC\u201905)","volume":"3729","author":"Friedrich","year":"2005"},{"key":"S0890060411000011_ref5","first-page":"381","article-title":"Using crude probability estimates to guide diagnosis","volume":"45","author":"DeKleer","year":"1990","journal-title":"AI Journal"},{"key":"S0890060411000011_ref20","doi-asserted-by":"crossref","unstructured":"Lin L. , & Jiang Y. (2003). The computation of hitting sets: review and new algorithm. Information Processing Letters 86, 177\u2013184.","DOI":"10.1016\/S0020-0190(02)00506-9"},{"key":"S0890060411000011_ref21","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.1996.569607"},{"key":"S0890060411000011_ref3","volume-title":"Planning, Scheduling and Constraint Satisfaction: From Theory to Practice","author":"Castillo","year":"2005"},{"key":"S0890060411000011_ref7","first-page":"97","article-title":"Diagnosing multiple faults","volume":"32","author":"DeKleer","year":"1987","journal-title":"AI Journal"},{"key":"S0890060411000011_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-007-0105-8"},{"key":"S0890060411000011_ref11","unstructured":"Felfernig A. , Friedrich G. , Schubert M. , Mandl M. , Mairitsch M. , & Teppan E. (2009). Plausible repairs for inconsistent requirements. Proc. 21st Int. Joint Conf. Artificial Intelligence (IJCAI\u201909), pp. 791\u2013796, Pasadena, CA."},{"key":"S0890060411000011_ref13","unstructured":"Fijany A. , & Vatan F. (2004). New approaches for efficient solutions of hitting set problems. Proc. Int. Symp. Information and Communication Technologies, pp. 1\u201310, Cancun, Mexico."},{"key":"S0890060411000011_ref14","doi-asserted-by":"publisher","DOI":"10.1109\/5254.708434"},{"key":"S0890060411000011_ref19","first-page":"95","article-title":"Computing minimal hitting sets with genetic algorithms","volume":"32","author":"Lin","year":"2002","journal-title":"Algorithmica"},{"key":"S0890060411000011_ref26","doi-asserted-by":"publisher","DOI":"10.1109\/MIS.2007.6"},{"key":"S0890060411000011_ref23","unstructured":"O'Sullivan B. , Papdopoulos A. , Faltings B. , & Pu P. (2007). Representative explanations for over-constrained problems. Proc. 22nd National Conf. Artificial Intelligence (AAAI\u201907), pp. 323\u2013328, Vancouver, Canada."},{"key":"S0890060411000011_ref24","first-page":"57","article-title":"A theory of diagnosis from first principles","volume":"23","author":"Reiter","year":"1987","journal-title":"AI Journal"},{"key":"S0890060411000011_ref27","volume-title":"Foundations of Constraint Satisfaction","author":"Tsang","year":"1993"},{"key":"S0890060411000011_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00166-6"},{"key":"S0890060411000011_ref22","unstructured":"Mittal S. , & Frayman F. (1989). Towards a generic model of configuration tasks. Proc. 11th Int. Joint Conf. Artificial Intelligence (IJCAI\u201989), pp. 1395\u20131401, Detroit, MI."},{"key":"S0890060411000011_ref6","first-page":"197","article-title":"Characterizing diagnoses and systems","volume":"56","author":"DeKleer","year":"1992","journal-title":"AI Journal"},{"key":"S0890060411000011_ref1","first-page":"93","article-title":"A framework for the development of personalized, distributed web-based configuration systems","volume":"24","author":"Ardissono","year":"2003","journal-title":"AI Magazine"}],"container-title":["Artificial Intelligence for Engineering Design, Analysis and Manufacturing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0890060411000011","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T21:39:57Z","timestamp":1556228397000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0890060411000011\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,10]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["S0890060411000011"],"URL":"https:\/\/doi.org\/10.1017\/s0890060411000011","relation":{},"ISSN":["0890-0604","1469-1760"],"issn-type":[{"value":"0890-0604","type":"print"},{"value":"1469-1760","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6,10]]}}}