Abstract
We present an improvement to the Hyper preprocessing algorithm that was suggested by Bacchus and Winter in SAT 2003 [1]. Given the power of modern SAT solvers, Hyper is currently one of the only cost-effective preprocessors, at least when combined with some modern SAT solvers and on certain classes of problems. Our algorithm, although it produces less information than Hyper, is much more efficient. Experiments on a large set of industrial Benchmark sets from previous SAT competitions show that HyperBinFast is always faster than Hyper (sometimes an order of magnitude faster on some of the bigger CNF formulas), and achieves faster total run times, including the SAT solver’s time. The experiments also show that HyperBinFast is cost-effective when combined with three state-of-the-art SAT solvers.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bacchus, F., Winter, J.: Effective preprocessing with hyper-resolution and equality reduction. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 341–355. Springer, Heidelberg (2004)
Gershman, R., Strichman, O.: Cost-effective hyper-resolution for preprocessing cnf formulas (full version) (2005), www.cs.technion.ac.il/~gershman/papers/sat05_full.pdf
Ryan, L.: Efficient algorithms for clause-learning SAT solvers. Master’s thesis, Simon Fraser University (2004)
Silva, J.P.M., Sakallah, K.A.: GRASP - a new search algorithm for satisfiability. Technical Report TR-CSE-292996, Univerisity of Michigen (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gershman, R., Strichman, O. (2005). Cost-Effective Hyper-Resolution for Preprocessing CNF Formulas. In: Bacchus, F., Walsh, T. (eds) Theory and Applications of Satisfiability Testing. SAT 2005. Lecture Notes in Computer Science, vol 3569. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11499107_34
Download citation
DOI: https://doi.org/10.1007/11499107_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26276-3
Online ISBN: 978-3-540-31679-4
eBook Packages: Computer ScienceComputer Science (R0)