Literal-Based MCS Extraction

Abstract

Given an over-constrained system, a Maximal Satisfiable Subset (MSS) denotes a maximal set of constraints that are consistent. A Minimal Correction Subset (MCS, or co-MSS) is the complement of an MSS. MSSes/MCSes find a growing range of practical applications, including optimization, configuration and diagnosis. A number of MCS extraction algorithms have been proposed in recent years, enabling very significant performance gains. This paper builds on earlier work and proposes a finer-grained view of the MCS extraction problem, one that reasons in terms of literals instead of clauses. This view is inspired by the relationship between MCSes and backbones of propositional formulas, which is further investigated, and allows for devising a novel algorithm. Also, the paper develops a number of techniques to approximate (weighted partial) MaxSAT by a selective enumeration of MCSes. Empirical results show substantial improvements over the state of the art in MCS extraction and indicate that MCS-based MaxSAT approximation is very effective in practice.