Premium
A hybrid algorithm for finding minimal unsatisfiable subsets in over‐constrained CSPs
Author(s) -
Shah I.
Publication year - 2011
Publication title -
international journal of intelligent systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.291
H-Index - 87
eISSN - 1098-111X
pISSN - 0884-8173
DOI - 10.1002/int.20497
Subject(s) - constraint satisfaction problem , hybrid algorithm (constraint satisfaction) , computer science , set (abstract data type) , algorithm , constraint satisfaction , constraint (computer aided design) , branch and bound , mathematical optimization , mathematics , artificial intelligence , local consistency , geometry , probabilistic logic , programming language
Minimal Unsatisfiable Subsets (MUSes) are the subsets of constraints of an overconstrained constraint satisfaction problem (CSP) that cannot be satisfied simultaneously and therefore are responsible for the conflict in the CSP. In this paper, we present a hybrid algorithm for finding MUSes in overconstrained CSPs. The hybrid algorithm combines the direct and the indirect approaches to finding MUSes in overconstrained CSPs. Experimentation with random CSPs reveals that the hybrid approach is not only quite efficient but when operating under a time bound it finds a more representative set of MUSes. © 2011 Wiley Periodicals, Inc.