zbMATH — the first resource for mathematics

Justification-based local search with adaptive noise strategies. (English) Zbl 1182.68247
Cervesato, Iliano (ed.) et al., Logic for programming, artificial intelligence, and reasoning. 15th international conference, LPAR 2008, Doha, Qatar, November 22–27, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-89438-4/pbk). Lecture Notes in Computer Science 5330. Lecture Notes in Artificial Intelligence, 31-46 (2008).
Summary: We study a framework called BC SLS for a novel type of stochastic local search (SLS) for propositional satisfiability (SAT). Aimed specifically at solving real-world SAT instances, the approach works directly on a non-clausal structural representation for SAT. This allows for don’t care detection and justification guided search heuristics in SLS by applying the circuit-level SAT technique of justification frontiers. In this paper we extend the BC SLS approach first by developing generalizations of BC SLS which are probabilistically approximately complete (PAC). Second, we develop and study adaptive noise mechanisms for BC SLS, including mechanisms based on dynamically adapting the waiting period for noise increases. Experiments show that a preliminary implementation of the novel adaptive, PAC generalization of the method outperforms a well-known CNF level SLS method with adaptive noise (AdaptNovelty+) on a collection of structured real-world SAT instances.
For the entire collection see [Zbl 1154.68007].
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
UBCSAT; UnitWalk
Full Text: DOI