Exploiting hypergraph partitioning for efficient Boolean satisfiability
Authors:
- 1 January 2004
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15526674,p. 141-146
Abstract
This paper presents hypergraph partitioning based constraint decomposition procedures to guide Boolean satisfiability search. Variable-constraint relationships are modeled on a hypergraph and partitioning based techniques are employed to decompose the constraints. Subsequently, the decomposition is analyzed to solve the CNF-SAT problem efficiently. The contributions of this research are two-fold: 1) to engineer a constraint decomposition technique using hypergraph partitioning; 2) to engineer a constraint resolution method based on this decomposition. Preliminary experiments show that our approach is fast, scalable and can significantly increase the performance (often orders of magnitude) of the SAT engine.Keywords
This publication has 9 references indexed in Scilit:
- Multilevel Hypergraph Partitioning: Application In Vlsi Domain2005
- Partition-based logical reasoning for first-order and propositional theoriesArtificial Intelligence, 2005
- BerkMin: A fast and robust SAT-solver2003
- GRASP-A new search algorithm for satisfiability2002
- Partition-based decision heuristics for image computation using SAT and BDDs2002
- Solving Satisfiability using Decomposition and the Most Constrained Subproblem (Preliminary Report)Electronic Notes in Discrete Mathematics, 2001
- Network-based heuristics for constraint-satisfaction problemsArtificial Intelligence, 1987
- A machine program for theorem-provingCommunications of the ACM, 1962
- A Computing Procedure for Quantification TheoryJournal of the ACM, 1960