Solving hard satisfiability problems with synchronous simulated annealing on the AP1000 multiprocessor

Research output: Contribution to journalArticlepeer-review

Abstract

Solving the hard Satisfiability Problem is difficult and time-consuming for even modest sized problem instances. This report presents a parallel synchronous simulated annealing method for solving the Random L-Sat problem on a large scale distributed-memory multiprocessor. In particular, we use a parallel synchronous simulated annealing method, called Generalized Speculative Computation, which guarantees the convergence property and same decision sequence of sequential simulated annealing. To demonstrate the performance, we have selected the Random L-SAT instances of 100-variable/425-clause to 5,000-variable/21,250-clause. Experimental results on the AP1000 distributed-memory multiprocessor indicate that the method can satisfy 99.9% of the clauses of the hard Random L-Sat instances while giving nearly 70-fold speedup on 500 processors.

Original languageEnglish (US)
Pages (from-to)719-722
Number of pages4
JournalIEEE Symposium on Parallel and Distributed Processing - Proceedings
StatePublished - Dec 1 1995

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Solving hard satisfiability problems with synchronous simulated annealing on the AP1000 multiprocessor'. Together they form a unique fingerprint.

Cite this