Justification-Based Local Search with Adaptive Noise Strategies

Reference:

Matti Järvisalo, Tommi Junttila, and Ilkka Niemelä. Justification-based local search with adaptive noise strategies. In Iliano Cervesato, Helmut Veith, and Andrei Voronkov, editors, Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR'08), volume 5330 of Lecture Notes in Computer Science, pages 31–46. Springer, 2008.

Abstract:

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.

Suggested BibTeX entry:

@inproceedings{JarvisaloJN:LPAR08,
    author = {Matti J{\"a}rvisalo and Tommi Junttila and Ilkka Niemel\"a},
    booktitle = {Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR'08)},
    editor = {Iliano Cervesato and Helmut Veith and Andrei Voronkov},
    pages = {31--46},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {Justification-Based Local Search with Adaptive Noise Strategies},
    volume = {5330},
    year = {2008},
}