Efficiently Exploiting Dependencies in Local Search for SAT

File Size Format
54264_1.pdf 133Kb Adobe PDF View
Title Efficiently Exploiting Dependencies in Local Search for SAT
Author Pham, Duc Nghia; Thornton, John Richard; Sattar, Abdul
Publication Title Proceedings of the 23rd AAAI Conference on Artificial Intelligence and the 20th Innovative Applications of Artificial Intelligence Conference
Editor Dieter Fox and Carla Gomes
Year Published 2008
Place of publication USA
Publisher AAAI Press
Abstract We propose a new local search platform that splits a CNF formula into three sub-components: i) a minimal dependency lattice (representing the core connections between logic gates), ii) a conjunction of equivalence clauses, and iii) the remaining clauses. We also adopt a new hierarchical cost function that focuses on solving the core components of the problem first. We then show experimentally that our platform not only significantly outperforms existing local search approaches but is also competitive with modern systematic solvers on highly structured problems.
Peer Reviewed Yes
Published Yes
Publisher URI http://www.aaai.org/Conferences/AAAI/aaai08.php
Alternative URI http://www.aaai.org/Library/AAAI/aaai08contents.php
Copyright Statement Copyright 2008 AAAI Press. This is the author-manuscript version of this paper. Reproduced in accordance with the copyright policy of the publisher. Use hypertext link for access to conference website.
ISBN 978-1-57735-368-3
Conference name 23rd AAAI Conference on Artificial Intelligence (AAAI-08)
Location Chicago, USA
Date From 2008-07-13
Date To 2008-07-17
URI http://hdl.handle.net/10072/23981
Date Accessioned 2009-03-11
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Artificial Intelligence and Image Processing
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Show simple item record

Griffith University copyright notice