Pre-processing in Boolean Satisfiability Using Bounded (2,k)-Consistency on Regions with Locally Difficult Constraint Setup
Abstract
A new type of partially global consistency derived from 2, -consistency called bounded 2, - consistency (B2C-consistency) is presented in this paper. It is designed for application in propositional satisfiability (SAT) as a building block for a preprocessing tool.
Together with the new B2C-consistency a special mechanism for selecting regions of the input SAT instance with difficult constraint setup was also proposed. This mechanism is used to select suitable difficult sub-problems whose simplification through consistency can lead to a significant reduction in the effort needed to solve the instance.
A new prototype preprocessing tool preprocessSIGMA which is based on the proposed techniques was implemented. As a proof of new concepts a competitive experimental evaluation on a set of relatively difficult SAT instances was conducted.
It showed that our prototype preprocessor is competitive with respect to the existent preprocessing tools LiVer, NiVer, HyPre, blocked clause elimination (BCE), and Shatter with saucy 3.0.