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 | http://www.cit.gu.edu.au/conferences/austai/ |
| Alternative URI | http://www.springer.com/computer/artificial/book/978-3-540-76926-2 |
| 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 www.springerlink.com. |
| 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 |
| URI | http://hdl.handle.net/10072/18345 |
| Date Accessioned | 2008-03-01 |
| Date Available | 2008-11-19T02:56:26Z |
| 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 |
Please use this identifier to cite this record: http://hdl.handle.net/10072/18345
Griffith University copyright notice
Copyright in individual works within the repository belongs to their authors or publishers. You may make a print or digital copy of a work for your personal non-commercial use. All other rights are reserved, except for fair dealings or other user rights granted by the copyright laws of your country.
Footer information
Back to top