The DOI matches its Crossref record; 107 of the 107 references it cites were found in a registry or an index.
Chaff: engineering an efficient SAT solver
Abstract
Boolean Satisfiability is probably the most studied of combinatorial optimization/search problems. Significant effort has been devoted to trying to provide practical solutions to this problem for problem instances encountered in a range of applications in Electronic Design Automation (EDA), as well as in Artificial Intelligence (AI). This study has culminated in the development of several SAT packages, both proprietary and in the public domain (e.g. GRASP, SATO) which find significant use in both research and industry. Most existing complete solvers are variants of the Davis-Putnam (DP) search algorithm. In this paper we describe the development of a new complete solver, Chaff, which achieves significant performance gains through careful engineering of all aspects of the search - especially a particularly efficient implementation of Boolean constraint propagation (BCP) and a novel low overhead decision strategy. Chaff has been able to obtain one to two orders of magnitude performance improvement on difficult SAT benchmarks in comparison with other solvers (DP or otherwise), including GRASP and SATO.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Goldberg, D. E., & Shakespeare, W. (2002) · Cited by 16,088
Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70356-x · Cited by 5,854
Glover, F. (1990) · ORSA Journal on Computing · doi:10.1287/ijoc.2.1.4 · Cited by 5,647
A machine program for theorem-proving
Davis, M., Logemann, G., & Loveland, D. (1962) · Communications of the ACM · doi:10.1145/368273.368557 · Cited by 3,220
Benchmarks for basic scheduling problems
Taillard, É. D. (1993) · European Journal of Operational Research · doi:10.1016/0377-2217(93)90182-m · Cited by 2,813
Symbolic Model Checking without BDDs
Biere, A., Cimatti, A., Clarke, E., & Zhu, Y. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49059-0_14 · Cited by 2,150
Local Search in Combinatorial Optimization
(2003) · Princeton University Press eBooks · doi:10.1515/9780691187563 · Cited by 2,057
de Kleer, J., & Williams, B. C. (1987) · Artificial Intelligence · doi:10.1016/0004-3702(87)90063-4 · Cited by 2,039
A new approach to the maximum-flow problem
Goldberg, A. V., & Tarjan, R. E. (1988) · Journal of the ACM · doi:10.1145/48014.61051 · Cited by 1,882
Cited by
Eén, N., & Sörensson, N. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24605-3_37 · Cited by 2,629
NuSMV 2: An OpenSource Tool for Symbolic Model Checking
Cimatti, A., Clarke, E., Giunchiglia, E., Giunchiglia, F., Pistore, M., Roveri, M., Sebastiani, R., & Tacchella, A. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45657-0_29 · Cited by 1,654
Handbook of Constraint Programming
(2006) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(06)x8001-x · Cited by 1,483
A Tool for Checking ANSI-C Programs
Clarke, E., Kroening, D., & Lerda, F. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24730-2_15 · Cited by 1,408
SCIP: solving constraint integer programs
Achterberg, T. (2009) · Mathematical Programming Computation · doi:10.1007/s12532-008-0001-1 · Cited by 1,167
Henzinger, T. A., Jhala, R., Majumdar, R., & Sutre, G. (2002) · Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/503272.503279 · Cited by 1,155
Satisfiability Modulo Theories
Barrett, C., & Tinelli, C. (2018) · Handbook of Model Checking · doi:10.1007/978-3-319-10575-8_11 · Cited by 1,122
Biere, A., Cimatti, A., Clarke, E. M., Strichman, O., & Zhu, Y. (2003) · Advances in Computers · doi:10.1016/s0065-2458(03)58003-2 · Cited by 952
Interpolation and SAT-Based Model Checking
McMillan, K. L. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45069-6_1 · Cited by 908
Simplify: a theorem prover for program checking
Detlefs, D., Nelson, G., & Saxe, J. B. (2005) · Journal of the ACM · doi:10.1145/1066100.1066102 · Cited by 786
Nieuwenhuis, R., Oliveras, A., & Tinelli, C. (2006) · Journal of the ACM · doi:10.1145/1217856.1217859 · Cited by 783
Translating Pseudo-Boolean Constraints into SAT
Eén, N., & Sörensson, N. (2006) · Journal on Satisfiability, Boolean Modeling and Computation · doi:10.3233/sat190014 · Cited by 587
SAT-Based Model Checking without Unrolling
Bradley, A. R. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-18275-4_7 · Cited by 548
Extending SAT Solvers to Cryptographic Problems
Soos, M., Nohl, K., & Castelluccia, C. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-02777-2_24 · Cited by 484
Potassco: The Potsdam Answer Set Solving Collection
Gebser, M., Kaufmann, B., Kaminski, R., Ostrowski, M., Schaub, T., & Schneider, M. (2011) · AI Communications · doi:10.3233/aic-2011-0491 · Cited by 456
Jhala, R., & Majumdar, R. (2009) · ACM Computing Surveys · doi:10.1145/1592434.1592438 · Cited by 418
Temporal Induction by Incremental SAT Solving
Eén, N., & Sörensson, N. (2003) · Electronic Notes in Theoretical Computer Science · doi:10.1016/s1571-0661(05)82542-3 · Cited by 382
A Survey of Automated Techniques for Formal Software Verification
D'Silva, V., Kroening, D., & Weissenbacher, G. (2008) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2008.923410 · Cited by 378
Machine Learning for Electronic Design Automation: A Survey
Huang, G., Hu, J., He, Y., Liu, J., Ma, M., Shen, Z., Wu, J., Xu, Y., Zhang, H., Zhong, K., et al. (2021) · ACM Transactions on Design Automation of Electronic Systems · doi:10.1145/3451179 · Cited by 341
Conflict-driven answer set solving: From theory to practice
Gebser, M., Kaufmann, B., & Schaub, T. (2012) · Artificial Intelligence · doi:10.1016/j.artint.2012.04.001 · Cited by 327
DPLL(T): Fast Decision Procedures
Ganzinger, H., Hagen, G., Nieuwenhuis, R., Oliveras, A., & Tinelli, C. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-27813-9_14 · Cited by 321
ManySAT: a Parallel SAT Solver
Hamadi, Y., Jabbour, S., & Sais, L. (2009) · Journal on Satisfiability, Boolean Modeling and Computation · doi:10.3233/sat190070 · Cited by 319
Answer Set Solving in Practice
Gebser, M., Kaminski, R., Kaufmann, B., & Schaub, T. H. (2012) · Synthesis lectures on artificial intelligence and machine learning · doi:10.2200/s00457ed1v01y201211aim019 · Cited by 288
Behavioral consistency of C and verilog programs using bounded model checking
Clarke, E., Kroening, D., & Yorav, K. (2003) · Proceedings of the 40th annual Design Automation Conference · doi:10.1145/775832.775928 · Cited by 281
A survey of recent advances in SAT-based formal verification
Prasad, M. R., Biere, A., & Gupta, A. (2005) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-004-0183-4 · Cited by 279
The Quest for Efficient Boolean Satisfiability Solvers
Zhang, L., & Malik, S. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45657-0_2 · Cited by 279
Self-citationThe verifying compiler: A grand challenge for computing research
Hoare, T. (2003) · Journal of the ACM · doi:10.1145/602382.602403 · Cited by 261
Learning action models from plan examples using weighted MAX-SAT
Yang, Q., Wu, K., & Jiang, Y. (2007) · Artificial Intelligence · doi:10.1016/j.artint.2006.11.005 · Cited by 206
“We then transform the constraints extracted from the plans into a weighted MAX-SAT representation [25,30,49], solve it and produce action models from the solution of the SAT problem.”
MethodHistory of Interactive Theorem Proving
Harrison, J., Urban, J., & Wiedijk, F. (2014) · Handbook of the History of Logic · doi:10.1016/b978-0-444-51624-4.50004-6 · Cited by 107
Efficient Exact Verification of Binarized Neural Networks
Jia, K., & Rinard, M. (2020) · arXiv · doi:10.48550/arxiv.2005.03597 · Cited by 33
(2013) · Journal of Machine Learning Research · Cited by 17
Metadata
- Authors
- Moskewicz, M. W., Madigan, C. F., Zhao, Y., Zhang, L., & Malik, S.
- Venue
- Proceedings of the 38th conference on Design automation - DAC '01
- Publisher
- ACM Press
- Published
- 2001
- Pages
- 530-535
- ISSN
- 0738-100X (ISSN-L)
- OpenAlex
- W2142785340
- Cited by
- 2,940
- References
- 107
- FWCI
- 75.54
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.