Variable Selection with PageRank for SAT Solvers
- 1 National Institute of Informatics, Japan
Abstract
How to choose decision variables often determines the performance of SAT solvers. In state-of-the-art SAT solvers, Variable State Independent Decaying Sum (VSIDS) has been used as a standard technique in the decision process. In this study, we analyze the VSIDS from the point of view of PageRank and propose a technique for improving the VSIDS. While the VSIDS focuses on local search spaces, the PageRank values are based on the relative importance from a global point of view. From this fact, we utilize the PageRank values for controlling the VSIDS and improve the performances of representative SAT solvers, MiniSAT and Glucose.
DOI: https://doi.org/10.3844/jcssp.2019.1074.1084
Copyright: © 2019 Tomohiro Sonobe. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 3,718 Views
- 1,623 Downloads
- 0 Citations
Download
Keywords
- SAT
- Solver
- PageRank
- Variable Selection