Title: Performance test of local search algorithms using new types of random CNF formulas
Abstract: New types of test-instance generators have been developed for generating random CNF (Conjunctive Normal Form) formulas with controlled attributes. In this paper, we use these generators to test the performance of local-search-based SAT algorithms. For this purpose, the generator which produces formulas having exactly one satisfying truth assignment is especially desirable. It is shown that (i) among several different strategies of local search, the weighting strategy is overwhelmingly faster than the others and that (ii) local search works significantly better for instances of larger clause/variable ratio, which allows us to come up with a new strategy for making local search even faster.
Publication Year: 1995
Publication Date: 1995-08-20
Language: en
Type: article
Access and Citation
Cited By Count: 52
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot