Adaptive Clause Weight Redistribution

File Size Format
40678.pdf 217Kb Adobe PDF View
Title Adaptive Clause Weight Redistribution
Author Ishtaiwi, Abdelraouf; Thornton, John; Anbulagen; Sattar, Abdul; Pham, Duc Nghia
Publication Title Principles and Practice of Constraint Programming - CP 2006
Editor Frederic Benhamou
Year Published 2006
Place of publication Berlin
Publisher Springer-Verlag
Abstract In recent years, dynamic local search (DLS) clause weighting algorithms have emerged as the local search state-of-the-art for solving propositional satisfiability problems. However, most DLS algorithms require the tuning of domain dependent parameters before their performance becomes competitive. If manual parameter tuning is impractical then various mechanisms have been developed that can automatically adjust a parameter value during the search. To date, the most effective adaptive clause weighting algorithm is RSAPS. However, RSAPS is unable to convincingly outperform the best non-weighting adaptive algorithm AdaptNovelty+, even though manually tuned clause weighting algorithms can routinely outperform the Novelty+ heuristic on which AdaptNovelty+ is based. In this study we introduce R+DDFW+, an enhanced version of the DDFWclause weighting algorithmdeveloped in 2005, that not only adapts the total amount of weight according to the degree of stagnation in the search, but also incorporates the latest resolution-based preprocessing approach used by the winner of the 2005 SAT competition (R+ AdaptNovelty+). In an empirical study we show R+DDFW+ improves on DDFW and outperforms the other leading adaptive (R+Adapt-Novelty+, R+RSAPS) and non-adaptive (R+G2WSAT) local search solvers over a range of random and structured benchmark problems.
Peer Reviewed Yes
Published Yes
Publisher URI http://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-173681505-0
Copyright Statement Copyright 2006 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 3-540-4627-8
Conference name 12th International Conference on the Principles and Practice of Constraint Programming (CP 2006)
Location Nantes, France
Date From 2006-09-24
Date To 2006-09-29
URI http://hdl.handle.net/10072/13102
Date Accessioned 2007-03-09
Date Available 2007-09-26T06:04:07Z
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Engineering and Information 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