Combining Adaptive and Dynamic Local Search for Satisfiability

There are no files associated with this record.

Title Combining Adaptive and Dynamic Local Search for Satisfiability
Author Pham, Duc Nghia; Thornton, John Richard; Gretton, Charles; Sattar, Abdul
Journal Name Journal on Satisfiability, Boolean Modeling and Computation
Editor Hans van Maaren (Editor-in-Chief)
Year Published 2008
Place of publication Netherlands
Publisher IOS Press
Abstract In this paper we describe a stochastic local search (SLS) procedure for finding models of satisfiable propositional formulae. This new algorithm, gNovelty+, draws on the features of two other WalkSAT family algorithms: AdaptNovelty+ and G2WSAT, while also successfully employing a hybrid clause weighting heuristic based on the features of two dynamic local search (DLS) algorithms: PAWS and (R)SAPS. 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, parameter tuning and resolution preprocessors on the performance of gNovelty+. The study compares gNovelty+ with three of the most representativeWalkSAT-based solvers: AdaptG2WSAT0, G2WSAT and 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 http://www.iospress.nl/journal/journal-on-satisfiability-boolean-modeling-and-computation/
Copyright Statement Self-archiving of the author-manuscript version is not yet supported by this journal. Please refer to the journal link for access to the definitive, published version or contact the author[s] for more information.
Volume 4
Page from 149
Page to 172
ISSN 1574-0617
Date Accessioned 2009-03-11
Date Available 2013-07-12T01:38:00Z
Language en_US
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Artificial Intelligence and Image Processing
URI http://hdl.handle.net/10072/23564
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Show simple item record

Griffith University copyright notice