Chapter 9. Preprocessing in SAT Solving
Armin Biere, Matti Järvisalo, Benjamin Kiesl
Abstract
Preprocessing has become a key component of the Boolean satisfiability (SAT) solving workflow. In practice, preprocessing is situated between the encoding phase and the solving phase, with the aim of decreasing the total solving time by applying efficient simplification techniques on SAT instances to speed up the search subsequently performed by a SAT solver. In this chapter, we overview key preprocessing techniques proposed in the literature. While the main focus is on techniques applicable to formulas in conjunctive normal form (CNF), we also selectively cover main ideas for preprocessing structural and higher-level SAT instance representations.
Topics & Concepts
PreprocessorBoolean satisfiability problemKey (lock)Computer scienceConjunctive normal formFocus (optics)Theoretical computer scienceWorkflowSatisfiabilityAlgorithmProgramming languageDatabaseOpticsPhysicsComputer securityModel-Driven Software Engineering Techniques