Building Structure into Local Search for SAT

There are no files associated with this record.

Title Building Structure into Local Search for SAT
Author Pham, Duc Nghia; Thornton, John Richard; Sattar, Abdul
Publication Title IJCAI-07, Proceedings of the 20th International Joint Conference on Artificial Intelligence
Editor Manuela Velosa
Year Published 2007
Abstract Local search procedures for solving satisfiability problems have attracted considerable attention since the development of GSAT in 1992. However, recent work indicates that for many real-world problems, complete search methods have the advantage, because modern heuristics are able to effectively exploit problem structure. Indeed, to develop a local search technique that can effectively deal with variable dependencies has been an open challenge since 1997. In this paper we show that local search techniques can effectively exploit information about problem structure producing significant improvements in performance on structured problem instances. Building on the earlier work of Ostrowski et al. we describe how information about variable dependencies can be built into a local search, so that only independent variables are considered for flipping. The cost effect of a flip is then dynamically calculated using a dependency lattice that models dependent variables using gates (specifically and, or and equivalence gates). The experimental study on hard structured benchmark problems demonstrates that our new approach significantly outperforms the previously reported best local search techniques.
Peer Reviewed Yes
Published Yes
Publisher URI http://www.ijcai.org/
Conference name International Joint Conference on Artificial Intelligence, IJCAI-07
Location Hyderabad, India
Date From 2007-01-06
Date To 2007-01-12
URI http://hdl.handle.net/10072/18331
Date Accessioned 2007-06-20
Date Available 2009-05-29T07:10:01Z
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject PRE2009-Other Artificial Intelligence
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Show simple item record

Griffith University copyright notice