On Computing Minimal Correction Subsets
| Dublin Core | PKP Metadata Items | Metadata for this Document | |
| 1. | Title | Title of document | On Computing Minimal Correction Subsets |
| 2. | Creator | Author's name, affiliation, country | Joao Marques-Silva; University College Dublin; Ireland |
| 2. | Creator | Author's name, affiliation, country | Federico Heras; University College Dublin; Ireland |
| 2. | Creator | Author's name, affiliation, country | Mikolas Janota; INESC-ID; Portugal |
| 2. | Creator | Author's name, affiliation, country | Alessandro Previti; University College Dublin; Ireland |
| 2. | Creator | Author's name, affiliation, country | Anton Belov; University College Dublin; Ireland |
| 3. | Subject | Discipline(s) | Artificial Intelligence, Computer Science |
| 3. | Subject | Keyword(s) | Boolean Satisfiability; Over-Constrained Systems; Minimal Correction Subsets; MCSes |
| 4. | Description | Abstract | A set of constraints that cannot be simultaneously satisfied is over-constrained. Minimal relaxations and minimal explanations for over-constrained problems find many practical uses. For Boolean formulas, minimal relaxations of over-constrained problems are referred to as Minimal Correction Subsets (MCSes). MCSes find many applications, including the enumeration of MUSes. Existing approaches for computing MCSes either use a Maximum Satisfiability (MaxSAT) solver or iterative calls to a Boolean Satisfiability (SAT) solver. This paper shows that existing algorithms for MCS computation can be inefficient, and so inadequate, in certain practical settings. To address this problem, this paper develops a number of novel techniques for improving the performance of existing MCS computation algorithms. More importantly, the paper proposes a novel algorithm for computing MCSes. Both the techniques and the algorithm are evaluated empirically on representative problem instances, and are shown to yield the most efficient and robust solutions for MCS computation. |
| 5. | Publisher | Organizing agency, location | |
| 6. | Contributor | Sponsor(s) | SFI, Ireland; FCT, Portugal |
| 7. | Date | (YYYY-MM-DD) | 2013-06-29 |
| 8. | Type | Status & genre | Peer-reviewed Paper |
| 8. | Type | Type | |
| 9. | Format | File format | |
| 10. | Identifier | Universal Resource Indicator | https://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6922 |
| 11. | Source | Journal/conference title; vol., no. (year) | International Joint Conference on Artificial Intelligence; Twenty-Third International Joint Conference on Artificial Intelligence |
| 12. | Language | English=en | en |
| 14. | Coverage | Geo-spatial location, chronological period, research sample (gender, age, etc.) | |
| 15. | Rights | Copyright and permissions | Authors who submit to this conference agree to the following terms: a)Authors transfer their copyrights in their paper to the International Joint Conferences on Artificial Intelligence, Inc. (IJCAI), in order to deal with future requests for reprints, translations, anthologies, reproductions, excerpts, and other publications. This grant will include, without limitation, the entire copyright in the paper in all countries of the world, including all renewals, extensions, and reversions thereof, whether such rights currently exist or hereafter come into effect, and also the exclusive right to create electronic versions of the paper, to the extent that such right is not subsumed under copyright. b)Every named author warrants that he/she is the sole author and owner of the copyright in the paper, except for those portions shown to be in quotations; that the paper is original throughout; and that their right to make the grants set forth above is complete and unencumbered. If anyone brings any claim or action alleging facts that, if true, constitute a breach of any of the foregoing warranties, each author, individually and collectively, will hold harmless and indemnify IJCAI, their grantees, their licensees, and their distributors against any liability, whether under judgment, decree, or compromise, and any legal fees and expenses arising out of that claim or actions, and the undersigned will cooperate fully in any defense IJCAI may make to such claim or action. Moreover, each author agrees to cooperate in any claim or other action seeking to protect or enforce any right the author has granted to IJCAI in the paper. If any such claim or action fails because of facts that constitute a breach of any of the foregoing warranties, each author agrees to reimburse whomever brings such claim or action for expenses and attorney’s fees incurred therein. c) In return for these rights, IJCAI hereby grants to each author, and the employers for whom the work was performed, royalty-free permission to: |