Research Article Open Access

Variable Selection with PageRank for SAT Solvers

Tomohiro Sonobe1
  • 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.

Journal of Computer Science
Volume 15 No. 8, 2019, 1074-1084

DOI: https://doi.org/10.3844/jcssp.2019.1074.1084

Submitted On: 1 May 2019 Published On: 6 August 2019

How to Cite: Sonobe, T. (2019). Variable Selection with PageRank for SAT Solvers. Journal of Computer Science, 15(8), 1074-1084. https://doi.org/10.3844/jcssp.2019.1074.1084

  • 3,718 Views
  • 1,623 Downloads
  • 0 Citations

Download

Keywords

  • SAT
  • Solver
  • PageRank
  • Variable Selection