Structure-Based Satisfiability Checking: Analyzing and Harnessing the Potential

Reference:

Matti Järvisalo. Structure-Based Satisfiability Checking: Analyzing and Harnessing the Potential. Doctoral dissertation. Volume TKK-ICS-D10 of TKK Dissertations in Information and Computer Science, Helsinki University of Technology, Faculty of Information and Natural Sciences, Department of Information and Computer Science, Espoo, Finland, 2008. ISBN 978-951-22-9641-5 (print) / ISBN 978-951-22-9642-2 (online).

Abstract:

Constraint satisfaction deals with developing automated techniques for solving computationally hard problems in a declarative fashion. The main emphasis of this thesis is on constraint satisfaction techniques for the propositional satisfiability problem (SAT).

As solving techniques for propositional satisfiability have rapidly progressed during the last 15 years, implementations of decision procedures for SAT, so called SAT solvers, have been found to be extremely efficient as back-end search engines in solving large industrial-scale combinatorial problems. Since SAT solvers have become a standard tool for solving various real-world problem instances of increasing size and difficulty, there is a demand for more and more robust and efficient solvers. For understanding the success (and failures) of SAT solving in specific problem domains, it is important to investigate how different types of structural properties of SAT instances are related to the efficiency of solving the instances with different SAT-based constraint satisfaction techniques. This is the underlying motivation for this thesis.

The emphasis of the thesis is on search-based SAT solving techniques for solving structured real-world problems. The work focuses on selected topics related to the analysis and development of both complete and stochastic local search methods for SAT. Both experimental and proof complexity theoretic approaches are applied.

The main contributions are three-fold.

The work contributes to the analysis of structure-based branching heuristics. A proof complexity theoretic power hierarchy is established for DPLL and clause learning SAT solvers with various structure-based branching restrictions. The proof complexity theoretic results are complemented by a detailed experimental evaluation of the effects of structure-based branching on state-of-the-art SAT solvers. In connection with structure-based branching in SAT, the work introduces the Extended ASP Tableaux proof system in the context of answer set programming, which is a field closely related to SAT solving.

The work also contributes to the development of stochastic local search methods for structured real-world SAT instances. A novel non-clausal local search method for SAT is developed by incorporating the concept of justification frontiers previously applied in the context of complete non-clausal solvers. Variants of the method are analyzed with respect to approximate completeness, and adaptive noise mechanisms aimed specifically for the method are developed.

As a third point of view to structure in SAT, the work addresses the problem of generating hard satisfiable SAT instances for both DPLL-based and local search solvers by introducing the Regular XORSAT model. Additionally, techniques for applying XORSAT instances specifically for benchmarking equivalence reasoning techniques in SAT solvers are developed.

Keywords:

propositional satisfiability, SAT, clause learning, DPLL, stochastic local search, branching heuristics, proof complexity, Boolean circuits, non-clausal formulas, problem structure, backdoors, hard instances, adaptive noise strategies, probabilistically approximately complete, answer set programming

Suggested BibTeX entry:

@phdthesis{Jarvisalo:Dissertation,
    address = {Espoo, Finland},
    author = {Matti J\"arvisalo},
    note = {ISBN 978-951-22-9641-5 (print) / ISBN 978-951-22-9642-2 (online)},
    school = {Helsinki University of Technology, Faculty of Information and Natural Sciences, Department of Information and Computer Science},
    title = {Structure-Based Satisfiability Checking: Analyzing and Harnessing the Potential},
    type = {Doctoral dissertation. {V}olume {TKK-ICS-D10} of {TKK} {D}issertations in {I}nformation and {C}omputer {S}cience},
    year = {2008},
}