Performance Test of Local Search Algorithms Using New Types of Random CNF Formulas
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 304-310.
Abstract
New types of test -instance generators have been developed for gene rating random CNF (Conjunctive Normal Form) formulas with controlled attributes. In this paper, we use these generators to test the performance of localsearch-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 .
@inproceedings{ijcai1995p40,
title = {Performance Test of Local Search Algorithms Using New Types of Random CNF Formulas},
author = {Cha, Byungki and Iwama, Kazuo},
booktitle = {Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, {IJCAI-95}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Chris S. Mellish},
pages = {304--310},
year = {1995},
note = {Automated Reasoning},
url = {https://ijcai.org/proceedings/1995/40},
}
TY - CPAPER TI - Performance Test of Local Search Algorithms Using New Types of Random CNF Formulas AU - Cha, Byungki AU - Iwama, Kazuo T2 - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95 PB - International Joint Conferences on Artificial Intelligence PY - 1995 SP - 304 EP - 310 UR - https://ijcai.org/proceedings/1995/40 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
