TL;DR
This paper introduces a novel algorithm, erSSAT, for solving a specific type of probabilistic reasoning problem called E-MAJSAT. By adapting a clause selection technique from the field of Quantified Boolean Formulas (QBFs), erSSAT significantly outperforms existing methods in terms of speed and memory usage, while also providing valuable lower bounds for complex problems.
What Problem Does This Paper Address?
Many real-world problems involve uncertainty and randomness, such as making decisions under uncertain conditions, inferring the most likely hypothesis given noisy data, or planning in dynamic environments. Stochastic Boolean Satisfiability (SSAT) is a powerful formalism for modeling these problems, but solving SSAT formulas is computationally challenging, belonging to the same PSPACE-complete complexity class as Quantified Boolean Formulas (QBFs). While QBFs have seen significant research advancements, SSAT, particularly its E-MAJSAT fragment (exist-random quantified SSAT), has received less attention. E-MAJSAT is crucial for applications like probabilistic planning and inferring maximum a posteriori hypotheses. Existing methods for E-MAJSAT often struggle with scalability, either due to their reliance on traditional DPLL-based search or knowledge compilation techniques. This paper aims to bridge this gap by developing a more efficient and scalable solver for E-MAJSAT.
Methods
The core innovation of this paper is the adaptation of the clause selection technique, originally developed for QBF solvers, to the domain of E-MAJSAT. The proposed algorithm, erSSAT, works by:
- Clause Selection: For a given E-MAJSAT formula $\exists X \exists Y . \phi(X, Y)$, the algorithm introduces selection variables for each clause in $\phi$. An assignment to the existential variables $X$ "selects" a subset of clauses. This selection relation is managed by a separate SAT solver.
- Clause Containment Learning: This is the key learning mechanism. If an assignment $\tau$ to $X$ leads to a certain satisfying probability, the algorithm learns a "blocking clause." This clause prevents future assignments that select a superset of the currently selected clauses from being explored, effectively pruning the search space. This is based on the observation that if $\tau_1$ selects a set of clauses $C_1$ and $\tau_2$ selects a superset $C_2 \supseteq C_1$, then the conditional probability for $\tau_2$ cannot be higher than for $\tau_1$.
- Weighted Model Counting: For each selected assignment $\tau$ to $X$, a weighted model counter is used to compute the conditional satisfying probability of the remaining formula over $Y$. This is where the probabilistic aspect is handled.
- Enhancement Techniques: To further improve efficiency, three techniques are employed:
- Minimal Clause Selection: Ensures that the set of selected clauses is minimal, leading to stronger blocking clauses.
- Clause Subsumption: Simplifies the set of selected clauses by removing redundant ones.
- Partial Assignment Pruning: Optimizes the blocking clauses by removing unnecessary literals.
The algorithm iteratively explores assignments to $X$, computes conditional probabilities, and refines the blocking clauses until the entire search space for $X$ is exhausted.
Datasets
The paper evaluates erSSAT on two types of benchmarks:
- Random k-CNF Formulas: These were generated using the
cnfgenpackage, with varying numbers of variables, clause lengths, and clause-to-variable ratios. For conversion to E-MAJSAT, half of the variables were existentially quantified, and the rest were randomly quantified with a probability of 0.5. - Application Formulas: Seven families of formulas were collected from existing benchmarks and literature, covering problems like QBF satisfiability (Toilet-A, Conformant), probabilistic conformant planning (Sand-Castle), maximum satisfiability (MaxSat), quantitative information flow (QIF), program synthesis (PS), and probabilistic equivalence checking (MPEC). Some of these were adapted to fit the E-MAJSAT format.
No new benchmarks were introduced in this paper.
Key Insights and Ideas
- Leveraging QBF Techniques for SSAT: The paper demonstrates that successful techniques from QBF solving, like clause selection, can be effectively adapted to tackle SSAT problems, opening up new avenues for research in probabilistic reasoning.
- Clause Containment Learning as a Powerful Pruning Strategy: The core learning mechanism effectively prunes the search space by identifying and blocking assignments that are guaranteed not to yield a better solution, significantly improving scalability.
- Approximate Solutions and Lower Bounds: The algorithm naturally provides lower bounds on the satisfying probability throughout its execution. This is crucial for problems where exact solutions are computationally intractable, allowing for practical approximate solutions.
- Memory Efficiency: The use of selection variables and the focus on smaller subproblems (clauses) lead to significantly lower memory consumption compared to existing solvers.
Key Results
- Random k-CNF Formulas: erSSAT solved 216 out of 280 instances exactly and provided lower bounds for the remaining 64. It outperformed existing solvers like DC-SSAT and c2d in terms of exact solutions and significantly reduced memory usage (two orders of magnitude less than DC-SSAT and one order less than c2d).
- Application Formulas: erSSAT quickly derived tight lower bounds for many application formulas, often outperforming Max (a maximum model counter) in speed for similar bounds. For some families, erSSAT was able to derive lower bounds where other solvers timed out.
- Enhancement Techniques: The three proposed enhancement techniques (minimal clause selection, clause subsumption, and partial assignment pruning) collectively provided an average speedup of up to 31% on random formulas and helped solve more problems within the timeout limit on application formulas.
Limitations and Future Work
- Limitations:
- The paper focuses specifically on E-MAJSAT (exist-random quantified SSAT). The proposed approach might require modifications for SSAT formulas with more complex quantifier structures (e.g., mixed existential, universal, and random quantifiers).
- While efficient, the enhancement techniques introduce some computational overhead, which can sometimes lead to slower performance on certain application formulas where they don't offer significant pruning benefits.
- Future Work:
- The authors explicitly state their intention to extend their work to solve SSAT with general prefix structures, moving beyond the E-MAJSAT fragment.
- Further exploration of how to optimize the enhancement techniques for different problem classes could lead to even greater efficiency gains.
Summary updated