Affiliations: INESC-ID/IST, Technical University of Lisbon, Lisbon, Portugal. ines@sat.inesc-id.pt | Complex & Adaptive Systems Laboratory, School of Computer Science and Informatics, University College Dublin, Ireland. jpms@ucd.ie
Note: [] Address for correspondence: INESC-ID, Rua Alves Redol 9, 1000-029 Lisboa, Portugal
Abstract: The extraction of a Minimal Unsatisfiable Core (MUC) in a Constraint Satisfaction Problem (CSP) aims to identify a subset of constraints that make a CSP instance unsatisfiable. Recent work has addressed the identification of a Minimal Set of Unsatisfiable Tuples (MUST) in order to restore the CSP satisfiability with respect to that MUC. A two-step algorithm has been proposed: first, a MUC is identified, and second, a MUST in the MUC is identified. This paper proposes an integrated algorithm for restoring satisfiability in a CSP, making use of a MaxSAT solver. The proposed approach encodes the CSP instance as a partial MaxSAT instance, in such a way that solving the MaxSAT instance corresponds to identifying the smallest set of tuples to be removed from the CSP instance to restore satisfiability. Experimental results illustrate the feasibility of the approach.
Keywords: constraint satisfaction problems, minimal unsatisfiable cores, minimal set of unsatisfiable tuples, maximum satisfiability
