Institut für Theoretische Informatik, Algorithm Engineering

SAT Solving with distributed local search

  • Typ:Masterarbeit
  • Datum:2018
  • Betreuer:

    Tomas Balyo

  • Bearbeiter:

    Guangping Li

  • Links:PDF
  • Stochastic local search (SLS) is an elementary technique for solving combinational problems. In the first section of this paper, we introduce an efficient SLS heuristic solver for Boolean Satisfiability Problem (SAT), in which the decisions only based on the probability distribution. We experimentally evaluate and analyze the performance of our solver in a combination of different techniques, including simulated annealing and walkSAT. With formula partitioning, we introduce a parallel version of our solver in the second section. The parallelism improves the efficiency of the solver. Using different random generator in solving the sub-formula can bring further improvement in performance to our parallel solver.