Streamlining Variational Inference for Constraint Satisfaction Problems

Aditya Grover, Tudor Achim, Stefano Ermon

Abstract

Several algorithms for solving constraint satisfaction problems are based on survey propagation, a variational inference scheme used to obtain approximate marginal probability estimates for variable assignments. These marginals correspond to how frequently each variable is set to true among satisfying assignments, and are used to inform branching decisions during search; however, marginal estimates obtained via survey propagation are approximate and can be self-contradictory. We introduce a more general branching strategy based on streamlining constraints, which sidestep hard assignments to variables. We show that streamlined solvers consistently outperform decimation-based solvers on random k-SAT instances for several problem sizes, shrinking the gap between empirical performance and theoretical limits of satisfiability by 16.3% on average for k=3,4,5,6.

Introduction

Constraint Satisfaction Problems (CSPs), such as the Boolean Satisfiability (SAT) problem, are fundamental to various domains including hardware verification and AI planning. As the search space for these problems grows exponentially with the number of variables, solvers rely heavily on heuristics to guide branching decisions. A prominent technique, Survey Propagation (SP), utilizes message-passing to estimate the marginal probability of a variable being assigned a specific value.

The standard application of SP is Survey Inspired Decimation (SID), which identifies the most "confident" variable and fixes its value permanently. However, because SP provides only an approximation, early incorrect "hard" assignments can lead to contradictions from which the solver cannot recover, even when solutions exist. This paper introduces Survey Inspired Streamlining (SIS), a more robust branching strategy that "hedges bets" by employing flexible multi-variable constraints instead of rigid single-variable assignments.

Methodology: From Decimation to Streamlining

The core innovation of SIS is the transition from unary constraints (decimation) to disjunctive constraints (streamlining). In SID, if a variable $x_i$ is likely to be True, the constraint $(x_i = 1)$ is added, eliminating 50% of possible assignments for that variable. In contrast, SIS pairs two highly confident variables, $x_i$ and $x_j$, and adds a streamlining clause such as $(x_i \lor x_j)$. This "soft" commitment only eliminates 25% of the search space (the case where both are False), allowing the solver to prune the space more safely while remaining resilient to errors in approximate marginals.

Factor graph representation of a CSP, showing variables (circles) and constraints (squares).

The SIS algorithm iteratively runs SP to obtain marginals, pairs confident variables to create streamlining clauses, and repeats this process for a set number of iterations before concluding with standard decimation. Theoretically, decimation is shown to be an aggressive special case of streamlining. By using length-2 clauses, SIS finds a middle ground that respects the SP "signal" while accounting for its inherent noise.

Experimental Results

The researchers evaluated SIS against SID on random $k$-SAT instances for $k \in \{3, 4, 5, 6\}$, focusing on constraint densities near the "phase transition" threshold where problems are most difficult.

Solver success rates for SIS (green) vs. SID (blue) across $k=3, 4, 5, 6$ as a function of constraint density $\alpha$. The red line indicates the theoretical phase transition.

As shown in the results, SIS consistently outperforms SID across all tested values of $k$. On average, SIS reduced the gap between empirical solver performance and theoretical satisfiability limits by 16.3%. Furthermore, SIS demonstrated increased robustness; while 36% of SID failures were due to the solver becoming stuck in pathological simplified formulas, this rate dropped to 24% for SIS. The method also proved effective as a pre-processor for competitive ensemble solvers like Dimetheus, significantly boosting success rates on high-density problems.

Conclusion and Future Work

Survey Inspired Streamlining provides a powerful generalization of decimation that significantly improves the performance of CSP solvers. By guiding the search toward clusters of satisfying assignments rather than individual solutions, SIS makes the remaining problem more tractable for local search algorithms.

Future work includes addressing the increased graph complexity introduced by streamlining constraints, which can occasionally hinder SP convergence. Additionally, integrating SIS with backtracking search mechanisms (e.g., CDCL) and exploring joint marginals for variable pairing could further enhance the efficacy of this streamlining approach.

Summary updated

Abstract

Several algorithms for solving constraint satisfaction problems are based on survey propagation, a variational inference scheme used to obtain approximate marginal probability estimates for variable assignments. These marginals correspond to how frequently each variable is set to true among satisfying assignments, and are used to inform branching decisions during search; however, marginal estimates obtained via survey propagation are approximate and can be self-contradictory. We introduce a more general branching strategy based on streamlining constraints, which sidestep hard assignments to variables. We show that streamlined solvers consistently outperform decimation-based solvers on random k-SAT instances for several problem sizes, shrinking the gap between empirical performance and theoretical limits of satisfiability by 16.3% on average for k=3,4,5,6.
BibTeX
@inproceedings{grover2018streamlining,
  author = {Aditya Grover and Tudor Achim and Stefano Ermon},
  title = {{Streamlining Variational Inference for Constraint Satisfaction Problems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=BJZcJd-uWH},
}
Figure