The Effect of Structural Branching on the Efficiency of Clause Learning SAT Solving: An Experimental Study (2008)

AUTHORS:

ABSTRACT:

The techniques for making decisions (branching), play a central role in complete methods for solving structured instances of propositional satisfiability (SAT). Experimental case studies in specific problem domains have shown that in some cases SAT solvers can determine satisfiability faster if branching in the solver is restricted to a subset of the variables at hand. The underlying idea in these approaches is to prune the search space substantially by restricting branching to strong backdoor sets of variables which guarantee completeness of the search. In this paper we present an extensive experimental evaluation of the effects of structure-based branching restrictions on the efficiency of solving structural SAT instances. Previous work is extended in a number of ways. We study state-of-the-art solver techniques, including clause learning and related heuristics. We provide a thorough analysis of the effect of branching restrictions on the inner workings of the solver, going deeper than merely measuring the solution time. Extending previous studies which have focused on input-restricted branching, we also consider relaxed branching restrictions that are based on underlying structural properties of the variables.

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

@article{
    JarvisaloN:JARGOL_ini,
    author = {J\"arvisalo, Matti and Niemel{\"a}, Ilkka},
    title = "The Effect of Structural Branching on the Efficiency of Clause Learning {SAT} Solving: An Experimental Study",
    url = "http://www.tcs.hut.fi/~mjj/publications.shtml",
    journal = "Journal of Algorithms: Algorithms in Cognition, Informatics, and Logic",
    optpdf = "jarvisalo-niemela.jargol08.pdf",
    number = "1--3",
    volume = "63",
    flags = "public MCM ACPT copy",
    pages = "90--113",
    year = "2008",
    keywords = "Backdoor sets, branching heuristics, clause learning, problem structure, propositional satisfiability",
    abstract = "The techniques for making decisions (branching), play a central role in complete methods for solving structured instances of propositional satisfiability (SAT). Experimental case studies in specific problem domains have shown that in some cases SAT solvers can determine satisfiability faster if branching in the solver is restricted to a subset of the variables at hand. The underlying idea in these approaches is to prune the search space substantially by restricting branching to strong backdoor sets of variables which guarantee completeness of the search. In this paper we present an extensive experimental evaluation of the effects of structure-based branching restrictions on the efficiency of solving structural SAT instances. Previous work is extended in a number of ways. We study state-of-the-art solver techniques, including clause learning and related heuristics. We provide a thorough analysis of the effect of branching restrictions on the inner workings of the solver, going deeper than merely measuring the solution time. Extending previous studies which have focused on input-restricted branching, we also consider relaxed branching restrictions that are based on underlying structural properties of the variables.",
    optps = "jarvisalo-niemela.jargol08.ps"
}

AUTHORS:

ABSTRACT:

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

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