Advances in Local Search for Satisfiability

File Size Format
49556_1.pdf 247Kb Adobe PDF View
Title Advances in Local Search for Satisfiability
Author Pham, Duc Nghia; Thornton, John Richard; Gretton, Charles; Sattar, Abdul
Publication Title AI 2007: Advances in Artificial Intelligence
Editor Mehmet A. Orgun, John Thornton
Year Published 2007
Place of publication Heidelberg, Germany
Publisher Springer
Abstract In this paper we describe a stochastic local search (SLS) procedure for finding satisfying models of satisfiable propositional for- mulae. This new algorithm, gNovelty+, draws on the features of two other WalkSAT family algorithms: R+AdaptNovelty+ and G2WSAT, while also successfully employing a dynamic local search (DLS) clause weighting heuristic to further improve performance. gNovelty+ was a Gold Medal winner in the random category of the 2007 SAT competition. In this paper we present a detailed description of the algorithm and extend the SAT competition results via an empirical study of the effects of problem structure and parameter tuning on the perfor- mance of gNovelty+. The study also compares gNovelty+ with two of the most representative WalkSAT-based solvers: G2WSAT, AdaptNovelty+ , and two of the most representative DLS solvers: RSAPS and PAWS. Our new results augment the SAT competition results and show that gNovelty+ is also highly competitive in the domain of solving structured satisfiability problems in comparison with other SLS techniques.
Peer Reviewed Yes
Published Yes
Publisher URI
Alternative URI
Copyright Statement Copyright 2007 Springer. This is the author-manuscript version of this paper. Reproduced in accordance with the copyright policy of the publisher. The original publication is available at
ISBN 978-3-540-76926-2
Conference name Australian Joint Conference on Artificial Intelligence
Location Gold Coast, Australia
Date From 2007-12-02
Date To 2007-12-06
Date Accessioned 2008-03-01
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Other Artificial Intelligence
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Show simple item record

Griffith University copyright notice