The DOI matches its Crossref record; 15 of the 15 references it cites were found in a registry or an index.
GRASP: a search algorithm for propositional satisfiability
Abstract
This paper introduces GRASP (Generic seaRch Algorithm for the Satisfiability Problem), a new search algorithm for Propositional Satisfiability (SAT). GRASP incorporates several search-pruning techniques that proved to be quite powerful on a wide variety of SAT problems. Some of these techniques are specific to SAT, whereas others are similar in spirit to approaches in other fields of Artificial Intelligence. GRASP is premised on the inevitability of conflicts during the search and its most distinguishing feature is the augmentation of basic backtracking search with a powerful conflict analysis procedure. Analyzing conflicts to determine their causes enables GRASP to backtrack nonchronologically to earlier levels in the search tree, potentially pruning large portions of the search space. In addition, by "recording" the causes of conflicts, GRASP can recognize and preempt the occurrence of similar conflicts later on in the search. Finally, straightforward bookkeeping of the causality chains leading up to conflicts allows GRASP to identify assignments that are necessary for a solution to be found. Experimental results obtained from a large number of benchmarks indicate that application of the proposed conflict analysis techniques to SAT algorithms can be extremely effective for a large number of representative classes of SAT instances.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
A Computing Procedure for Quantification Theory
Davis, M., & Putnam, H. (1960) · Journal of the ACM · doi:10.1145/321033.321034 · Cited by 2,647
de Kleer, J. (1986) · Artificial Intelligence · doi:10.1016/0004-3702(86)90080-9 · Cited by 1,736
A new method for solving hard satisfiability problems
Selman, B., Levesque, H. J., & Mitchell, D. G. M. (1992) · Cited by 1,156
Stallman, R. M., & Sussman, G. J. (1977) · Artificial Intelligence · doi:10.1016/0004-3702(77)90029-7 · Cited by 712
Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition
Dechter, R. (1990) · Artificial Intelligence · doi:10.1016/0004-3702(90)90046-3 · Cited by 497
Ginsberg, M. L. (1993) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1 · Cited by 456
Combinational test generation using satisfiability
Stephan, P., Brayton, R. K., & Sangiovanni-Vincentelli, A. L. (1996) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.536723 · Cited by 326
Improvements to propositional satisfiability search algorithms
Freeman, J. (1995) · Cited by 265
Experimental results on the crossover point in satisfiability problems
Crawford, J. M., & Auton, L. D. (1993) · Cited by 209
An Outlook on Truth Maintenance.
McAllester, D. (1980) · Defense Technical Information Center (DTIC) · Cited by 178
A transitive closure algorithm for test generation
Chakradhar, S. T., Agrawal, V. D., & Rothweiler, S. G. (1993) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.238038 · Cited by 172
Some results and experiments in programming techniques for propositional logic
Blair, C., Jeroslow, R. G., & Lowe, J. K. (1986) · Computers & Operations Research · doi:10.1016/0305-0548(86)90056-0 · Cited by 122
A rearrangement search strategy for determining propositional satisfiability
Zabih, R., & McAllester, D. (1988) · Cited by 104
Algorithms for testing the satisfiability of propositional formulae
Gallo, G., & Urbani, G. (1989) · The Journal of Logic Programming · doi:10.1016/0743-1066(89)90009-5 · Cited by 94
Cited by
Chaff: engineering an efficient SAT solver
Moskewicz, M. W., Madigan, C. F., Zhao, Y., Zhang, L., & Malik, S. (2001) · Proceedings of the 38th conference on Design automation - DAC '01 · doi:10.1145/378239.379017 · Cited by 2,940
Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks
Katz, G., Barrett, C., Dill, D. L., Julian, K., & Kochenderfer, M. J. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-63387-9_5 · Cited by 1,706
SCIP: solving constraint integer programs
Achterberg, T. (2009) · Mathematical Programming Computation · doi:10.1007/s12532-008-0001-1 · Cited by 1,167
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
A survey on new generation metaheuristic algorithms
Dokeroglu, T., Sevinc, E., Kucukyilmaz, T., & Cosar, A. (2019) · Computers & Industrial Engineering · doi:10.1016/j.cie.2019.106040 · Cited by 923
Metadata
- Authors
- Marques-Silva, J. P., & Sakallah, K. A.
- Venue
- IEEE Transactions on Computers
- Published
- 1999-05
- Volume
- 48
- Issue
- 5
- Pages
- 506-521
- ISSN
- 0018-9340 (ISSN-L)
- OpenAlex
- W2044560939
- Cited by
- 1,374
- References
- 15
- FWCI
- 53.97
- Type
- journal article
- 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.