A Method to Avoid Duplicative Flipping in Local Search for SAT
Paper
Paper/Presentation Title | A Method to Avoid Duplicative Flipping in Local Search for SAT |
---|---|
Presentation Type | Paper |
Authors | Duong, Thach-Thao (Author), Pham, Duc Nghia (Author) and Sattar, Abdul (Author) |
Editors | Thielscher, Michael and Zhang, Dongmo |
Journal or Proceedings Title | Lecture Notes in Artificial Intelligence (Book series) |
ERA Conference ID | 42498 |
Journal Citation | 7691, pp. 218-229 |
Number of Pages | 12 |
Year | 2012 |
Place of Publication | Berlin |
ISBN | 9783642351006 |
9783642351013 | |
Digital Object Identifier (DOI) | https://doi.org/10.1007/978-3-642-35101-3_19 |
Web Address (URL) of Paper | https://link.springer.com/chapter/10.1007/978-3-642-35101-3_19 |
Conference/Event | 25th Australasian Joint Conference on Artificial Intelligence (AI 2012) |
Australasian Joint Conference on Artificial Intelligence | |
Event Details | Australasian Joint Conference on Artificial Intelligence AI Rank B B B B B B B |
Event Details | 25th Australasian Joint Conference on Artificial Intelligence (AI 2012) Event Date 04 to end of 07 Dec 2012 Event Location Sydney, Australia |
Abstract | Stochastic perturbation on variable flipping is the key idea of local search for SAT. Observing that variables are flipped several times in an attempt to escape from a local minimum, this paper presents a duplication learning mechanism in stagnation stages to minimise duplicative variable flipping. The heuristic incorporates the learned knowledge into a variable weighting scheme to effectively prevent the search from selecting duplicative variables. Additionally, probability-based and time window smoothing techniques are adopted to eliminate the effects of redundant information. The integration of the heuristic and gNovelty + was compared with the original solvers and other state-of-the-art local search solvers. The experimental results showed that the new solver outperformed other solvers on the full set of SAT 2011 competition instances and three sets of real-world verification problems. |
Keywords | Learning mechanism; Local minimums; Local search; Redundant informations; Smoothing techniques; Stochastic perturbations; Time windows; Variable weighting; Verification problems |
ANZSRC Field of Research 2020 | 460210. Satisfiability and optimisation |
Byline Affiliations | Griffith University |
Institution of Origin | University of Southern Queensland |
https://research.usq.edu.au/item/q7119/a-method-to-avoid-duplicative-flipping-in-local-search-for-sat
65
total views2
total downloads2
views this month0
downloads this month