Introduction
Modern SAT solvers are among the most successful automated reasoning tools, capable of solving industrial instances with millions of variables and clauses. The key to their success lies in sophisticated algorithms and heuristics that go far beyond the basic DPLL algorithm. This article explores the techniques that make modern SAT solvers practical and powerful.
Historical Context
SAT solvers evolved dramatically from the 1990s onward. Early solvers like GRASP and Chaff introduced conflict-driven clause learning (CDCL), which revolutionized SAT solving. Subsequent improvements in variable ordering heuristics, restart strategies, and preprocessing techniques made SAT solvers practical for industrial applications. Today, SAT solvers are used in hardware verification, software testing, and many other domains.
Conflict-Driven Clause Learning (CDCL)
Core Idea
Principle: When a conflict is found, analyze it to learn a new clause that prevents similar conflicts
Benefit: Dramatically reduces search space by avoiding redundant work
Conflict Analysis
Process:
- Detect conflict (empty clause derived)
- Trace back through implications
- Identify variables causing conflict
- Learn clause preventing this conflict
Example:
Conflict: (¬x ∨ ¬y ∨ ¬z) and (x ∨ y ∨ z) both false
Analysis: x, y, z all assigned to satisfy first clause
Learning: At least one of x, y, z must be unassigned
Learned clause: (x ∨ y ∨ z)
Implication Graph
Structure: Directed graph showing variable assignments and their causes
Nodes: Variable assignments Edges: Implications (if A then B)
Conflict Analysis: Trace back through graph to find conflict cause
Variable Ordering Heuristics
Static Ordering
Strategy: Order variables before search begins
Disadvantage: Doesn’t adapt to problem structure
Dynamic Ordering
Strategy: Choose variable during search based on current state
Advantages: Adapts to problem, often more effective
VSIDS (Variable State Independent Decaying Sum)
Idea: Track how often variables appear in conflicts
Algorithm:
- Initialize activity for each variable to 0
- When variable appears in conflict, increase activity
- Periodically decay all activities
- Choose variable with highest activity
Benefit: Focuses on variables causing conflicts
Other Heuristics
Jeroslow-Wang: Favor variables in short clauses MOMs (Maximum Occurrences in Minimum clauses): Choose variable appearing most in shortest clauses Berkmin: Similar to VSIDS but with different decay
Restart Strategies
Why Restart?
Problem: Search can get stuck in unproductive branches
Solution: Restart search with learned clauses
Benefit: Learned clauses guide new search more effectively
Restart Policies
Fixed Interval: Restart every k conflicts
- Simple but may restart too often or too rarely
Adaptive: Adjust restart frequency based on progress
- More sophisticated, often more effective
Luby Sequence: Restart at intervals following Luby sequence
- Theoretically motivated, good practical performance
Preprocessing and Simplification
Unit Propagation
Technique: Simplify formula by assigning unit clauses
Benefit: Reduces problem size
Pure Literal Elimination
Technique: Assign variables appearing only positive or negative
Benefit: Reduces problem size
Subsumption
Technique: Remove clauses subsumed by others
Example: Remove (x ∨ y ∨ z) if (x ∨ y) exists
Benefit: Reduces problem size
Equivalent Literal Substitution
Technique: Identify equivalent literals and merge them
Benefit: Reduces variables
Inprocessing
Idea: Apply simplifications during search, not just before
Techniques:
- Clause learning
- Subsumption
- Variable elimination
Benefit: Adapts simplifications to search progress
Practical SAT Solvers
MiniSat
Characteristics: Minimalist, clean implementation Strengths: Educational, good baseline Weaknesses: Not optimized for large instances
CaDiCaL
Characteristics: Modern, highly optimized Strengths: Competitive performance, good for industrial instances Weaknesses: Complex implementation
Glucose
Characteristics: Focuses on clause learning Strengths: Good at learning useful clauses Weaknesses: May use more memory
Kissat
Characteristics: Recent solver with modern techniques Strengths: Fast, competitive Weaknesses: Still evolving
Parallel SAT Solving
Portfolio Approach
Idea: Run multiple solvers with different strategies in parallel
Benefit: Different strategies work better on different instances
Clause Sharing
Idea: Share learned clauses between parallel solvers
Benefit: Learned clauses help other solvers
Load Balancing
Challenge: Distribute work evenly among processors
Solution: Dynamic work distribution
SAT Solver Evaluation
Benchmarks
SAT Competition: Annual competition with diverse instances Industrial Benchmarks: Real-world problems from applications Crafted Benchmarks: Designed to test specific techniques
Metrics
Solving Time: How fast solver finds solution Memory Usage: How much memory solver uses Scalability: How performance degrades with problem size
Applications of SAT Solvers
Hardware Verification
Application: Verify circuits satisfy specifications Process: Encode circuit and property as SAT Benefit: Catches design errors
Software Testing
Application: Generate test cases Process: Encode program and test requirements as SAT Benefit: Automated test generation
Planning
Application: Find valid plans Process: Encode planning problem as SAT Benefit: Optimal plans
Cryptanalysis
Application: Break cryptographic systems Process: Encode cryptographic equations as SAT Benefit: Analyze security
Glossary
CDCL: Conflict-driven clause learning
Conflict: Situation where formula is unsatisfiable
Implication Graph: Graph showing variable assignments and causes
Inprocessing: Simplification during search
Learned Clause: Clause derived from conflict analysis
Preprocessing: Simplification before search
Restart: Restart search with learned clauses
VSIDS: Variable state independent decaying sum
Practice Problems
Problem 1: Explain how CDCL improves over basic DPLL.
Solution: CDCL learns clauses from conflicts, preventing similar conflicts in future search. This dramatically reduces search space compared to basic DPLL which just backtracks.
Problem 2: Describe how VSIDS heuristic works.
Solution: VSIDS tracks how often variables appear in conflicts. Variables appearing frequently in conflicts get higher priority. This focuses search on variables causing problems.
Problem 3: Why is restarting beneficial in SAT solving?
Solution: Restarting allows the solver to explore different branches with the benefit of learned clauses. This helps escape unproductive search paths and often finds solutions faster.
Related Resources
- SAT Solvers: https://en.wikipedia.org/wiki/SAT_solver
- CDCL: https://en.wikipedia.org/wiki/Conflict-driven_clause_learning
- MiniSat: http://minisat.se/
- CaDiCaL: https://github.com/arminbiere/cadical
- Glucose: http://www.labri.fr/perso/lsimon/glucose/
- Kissat: https://github.com/arminbiere/kissat
- SAT Competition: http://www.satcompetition.org/
- Boolean Satisfiability: https://en.wikipedia.org/wiki/Boolean_satisfiability_problem
- DPLL Algorithm: https://en.wikipedia.org/wiki/DPLL_algorithm
- Automated Reasoning: https://en.wikipedia.org/wiki/Automated_reasoning
- Formal Verification: https://en.wikipedia.org/wiki/Formal_verification
- Constraint Satisfaction: https://en.wikipedia.org/wiki/Constraint_satisfaction_problem
- SMT Solvers: https://en.wikipedia.org/wiki/Satisfiability_modulo_theories
- Parallel SAT: https://en.wikipedia.org/wiki/Parallel_SAT_solving
- SAT Applications: https://en.wikipedia.org/wiki/SAT_solver#Applications
Conclusion
Modern SAT solvers represent a remarkable achievement in automated reasoning. By combining sophisticated algorithms (CDCL), intelligent heuristics (VSIDS), and engineering optimizations, SAT solvers have become practical tools for solving real-world problems with millions of variables.
Understanding SAT solver techniques is essential for anyone working with automated reasoning, formal verification, or constraint solving. The success of SAT solvers demonstrates how theoretical insights combined with practical engineering can overcome computational complexity.
Comments