Journal of Computer Science

Variable Selection with PageRank for SAT Solvers

Tomohiro Sonobe

DOI : 10.3844/jcssp.2019.1074.1084

Journal of Computer Science

Volume 15, Issue 8

Pages 1074-1084

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.

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.