Home | english  | Impressum | Datenschutz | Sitemap | KIT

SAT Solving with distributed local search

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.