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.

@inproceedings{
    JarvisaloJN:LPAR08_ini,
    editor = "Cervesato, Iliano and Veith, Helmut and Voronkov, Andrei",
    author = {J{\"a}rvisalo, Matti and Junttila, Tommi and Niemel\"a, Ilkka},
    publisher = "Springer",
    title = "Justification-Based Local Search with Adaptive Noise Strategies",
    url = "http://www.tcs.tkk.fi/~mjj/publications.shtml",
    series = "Lecture Notes in Computer Science",
    booktitle = "Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR'08)",
    pages = "31--46",
    volume = "5330",
    flags = "MCM public copy",
    year = "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."
}

AUTHORS:

ABSTRACT:

URL:
http://www.tcs.tkk.fi/~mjj/publications.shtml

AUTHORS:

ABSTRACT:

URL: http://www.tcs.tkk.fi/~mjj/publications.shtml

URL:
http://www.tcs.tkk.fi/~mjj/publications.shtml