Core-Guided Minimal Correction Set and Core Enumeration

Core-Guided Minimal Correction Set and Core Enumeration

Nina Narodytska, Nikolaj Bjørner, Maria-Cristina Marinescu, Mooly Sagiv

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1353-1361. https://doi.org/10.24963/ijcai.2018/188

A set of constraints is unsatisfiable if there is no solution that satisfies these constraints. To analyse unsatisfiable problems, the user needs to understand where inconsistencies come from and how they can be repaired. Minimal unsatisfiable cores and correction sets are important subsets of constraints that enable such analysis. In this work, we propose a new algorithm for extracting minimal unsatisfiable cores and correction sets simultaneously. Building on top of the relaxation and strengthening framework, we introduce novel techniques for extracting these sets. Our new solver significantly outperforms several state of the art algorithms on common benchmarks when it comes to extracting correction sets and compares favorably on core extraction.
Keywords:
Constraints and SAT: MaxSAT, MinSAT
Constraints and SAT: Constraints and SAT
Constraints and SAT: SAT