TL;DR
This paper introduces a novel algorithm for solving Stochastic Boolean Satisfiability (SSAT) problems with random-exist quantification. By leveraging modern SAT solvers and model counters as black-box engines, their approach significantly outperforms existing methods in both speed and memory usage, and importantly, can also provide approximate solutions when exact computation is infeasible.
What Problem Does This Paper Address?
Stochastic Boolean Satisfiability (SSAT) is a powerful formalism for modeling computational problems involving uncertainty, such as belief network inference and probabilistic planning. While SSAT shares the same PSPACE-complete complexity as Quantified Boolean Formulas (QBFs), it has received less attention. Existing SSAT solvers often rely on traditional DPLL-based search, which can be inefficient. This paper focuses on a specific type of SSAT formula: random-exist quantified formulas (Φ = ∃X∀Y.Φ), which are particularly relevant for applications like belief network inference and probabilistic circuit verification. The challenge is to efficiently solve these formulas, especially when exact solutions are computationally prohibitive, and to provide meaningful approximate solutions.
Methods
The core of the proposed solution, dubbed SolveRESSAT, is an algorithm that treats modern SAT solvers and weighted model counters as black-box engines. Instead of reimplementing these complex tools, SolveRESSAT orchestrates them. The algorithm iteratively selects assignments for the randomly quantified variables (X) and uses a SAT solver to check if the remaining formula (with existentially quantified variables Y) is satisfiable.
Key novelties include:
- Minterm Generalization: When an assignment to X is found to be satisfiable (SAT minterm), it's generalized into a "minimal satisfying assignment" (a cube). Similarly, for unsatisfiable assignments (UNSAT minterms), a "minimal conflicting assignment" is found. This generalization process efficiently captures multiple assignments with a single cube, significantly reducing the search space.
- Leveraging SAT/Model Counting Engines: The algorithm directly uses off-the-shelf SAT solvers (like MiniSat) and weighted model counters (like Cachet) as its computational backends. This allows it to benefit from advancements in these mature technologies.
- Approximate SSAT: The algorithm is inherently designed to provide approximate solutions. By imposing a runtime limit, it can derive upper and lower bounds on the satisfying probability, which is crucial for real-world applications where exact solutions are intractable.
Datasets
The paper evaluates its approach on three sets of benchmarks:
- Random k-CNF Formulas: Generated using
cnfgen, these are standard benchmarks for testing SAT/QBF solvers. - Strategic Companies Formulas: Derived from planning problems, these are structured instances that pose a challenge for solvers.
- Probabilistic Equivalence Checking (PEC) Formulas: These are generated from ISCAS benchmark circuits and represent a real-world application of SSAT for verifying probabilistic circuits.
Key Insights and Ideas
- Black-box approach is powerful: Using mature SAT solvers and model counters as engines is a highly effective strategy, allowing the algorithm to inherit their performance improvements.
- Minterm generalization is crucial: The ability to generalize SAT/UNSAT minterms into minimal satisfying/conflicting assignments is the key to the algorithm's efficiency, drastically reducing the number of cubes to process.
- Approximate SSAT is practical: The algorithm's ability to provide tight bounds on satisfying probability within a limited time is a significant advantage for real-world problems where exact computation is infeasible.
- Memory efficiency: The minterm generalization technique leads to a substantial reduction in memory consumption compared to previous DPLL-based methods.
Key Results
- Performance on Random k-CNF:
reSSATsolved all 300 selected formulas, outperforming the state-of-the-artDc-SSATsolver in both runtime (5x improvement) and memory usage (2 orders of magnitude reduction). - Performance on Strategic Companies:
reSSATsolved all 60 formulas, again showing significant improvements in runtime and memory (2 orders of magnitude reduction) compared toDc-SSAT. - Performance on PEC: For probabilistic equivalence checking,
reSSATwas able to derive tight bounds on satisfying probability within a short time (60 seconds), even whenDc-SSATfailed to compute exact solutions within 1000 seconds. In some cases, these bounds closely matched the exact probabilities.
Limitations and Future Work
- Focus on Random-Exist: The current work focuses specifically on random-exist quantified SSAT formulas (Φ = ∃X∀Y.Φ).
- Future Work: The authors intend to extend the proposed algorithm to handle arbitrary quantified SSAT formulas, which would broaden its applicability.
Summary updated