Modern Boolean Satisfiability (SAT) solvers are remarkably powerful, but their performance is heavily dictated by the size and structure of the formulas they navigate. As a solver explores a problem, it frequently encounters redundancy—both in the original formulation of the problem and within the new clauses it learns along the way.
Unmanaged redundancy acts as a severe computational bottleneck. To understand why, we have to look at the core engine of modern solvers: Boolean Constraint Propagation (BCP), or unit propagation. When a clause contains redundant literals or when identical sub-expressions are repeated across many clauses, BCP slows down. The solver spends valuable cycles processing information that adds no logical value, dragging down overall efficiency.
To combat this, a prominent research direction focuses on redundancy reduction and clause minimization. By systematically stripping away unnecessary literals, factoring out common sub-clauses, and even leveraging optimization techniques like MaxSAT and Linear Programming to find the tightest possible logical constraints, researchers have unlocked massive speedups for state-of-the-art solvers.
Streamlining the Formula: Literal and Subclause Elimination
Redundancy manifests in two primary ways: locally, as extra literals inside individual clauses, and structurally, as recurring patterns across the entire formula.
Local Redundancy: In-Processing Literal Minimization
When Conflict-Driven Clause Learning (CDCL) solvers encounter a contradiction, they analyze the conflict to generate a new clause that prevents the solver from making the same mistake again. However, these learned clauses often contain redundant literals that are not strictly necessary to maintain the logical implication.
Luo et al. demonstrated that this degradation can be mitigated by integrating literal minimization directly into the search loop (a practice known as in-processing). By strategically applying unit propagation to evaluate learned clauses before they are finalized, the authors showed that solvers can strip away these superfluous literals.
The intuition here is straightforward: shorter clauses are more potent. A clause with fewer literals requires fewer variable assignments before it becomes a "unit clause" (a clause where all literals but one are false). Consequently, minimized clauses trigger BCP much earlier in the search tree, allowing the solver to prune dead ends faster.
Structural Redundancy: Common Subclause Elimination
Sometimes, redundancy is baked into the problem design itself. Large, real-world SAT instances often feature identical sets of literals repeating across thousands of different clauses.
To address this, Yan et al. introduced Common Subclause Elimination (CSE). Think of CSE as algebraic factoring for propositional logic. If a specific subclause (e.g., $A \lor B$) appears repeatedly, the technique replaces it with a single new variable ($Z$), adding a small set of defining clauses ($Z \leftrightarrow A \lor B$). This structural transformation simplifies the problem text, leading to fewer overall literals and accelerating the propagation process across the entire formula.
The Optimization Paradox: Using MaxSAT and LP for Minimization
Perhaps the most elegant twist in this research direction is the use of heavy optimization tools inside the solver to minimize clauses. While it might seem counterintuitive to solve an optimization problem (which is typically harder) just to assist with a satisfiability problem, the exponential reduction in search space heavily outweighs the overhead.
MaxSAT-Driven Clause Minimization
In Satisfaction-Driven Clause Learning (SDCL), solvers have the freedom to prune the search space by learning redundant clauses based on witness assignments. Oliveras et al. proposed a novel way to optimize this process using a Maximum Satisfiability (MaxSAT) solver.
Instead of negating a full variable assignment to create a long, weak clause, the authors formulated a MaxSAT query to find the absolute smallest subset of the current assignment that still satisfies the pruning condition. In a follow-up study, Oliveras et al. showed that this optimization loop shrinks learned clauses to roughly 30% of their original size. These ultra-short clauses possess immense pruning power, enabling the solver to simulate powerful proof systems polynomially.
[Full Variable Assignment] ──► [Formulate MaxSAT Query] ──► [Extract Minimal Sub-Assignment] ──► [Negate to form Short, Potent Clause]
Reduced Cost Fixing via Linear Programming
This cross-pollination of optimization and satisfiability also flows in the other direction: using continuous optimization to streamline MaxSAT solving itself. Bacchus et al. adapted "reduced cost fixing"—a classic technique from Integer Programming—into MaxSAT solvers.
By solving a continuous Linear Programming (LP) relaxation of the MaxSAT instance, the solver computes bounds on how much the objective function would worsen if a given variable's truth value were flipped. If this "reduced cost" exceeds the gap between the current best solution and the lower bound, the status of that soft clause can be permanently fixed. This prunes the search space entirely from an optimization standpoint.
Supporting this paradigm, Bjørner et al. analyzed the structural "cores" discovered by core-guided MaxSAT solvers, demonstrating that understanding these underlying structures allows for even better compression of cardinality constraints and refined minimization procedures.
Why It Works: The Interplay of Hardness and Redundancy
To truly understand why minimization is so vital, it helps to look at how redundancy alters problem difficulty. Intuitively, one might think that removing clauses always makes a problem harder because it removes constraints. Indeed, early foundational work by the authors of Redundancy in Random SAT Formulas revealed that completely irredundant random formulas are consistently the most challenging for solvers, because they lack the accidental "shortcuts" or alternative propagation pathways that redundant clauses can provide.
However, in structured, real-world industrial instances, unmanaged redundancy behaves differently. It manifests as a drag coefficient on the solver's engine. Every redundant literal or duplicated subclause forces the solver to allocate memory, track watched literals, and execute unnecessary BCP steps.
Minimization works because it shifts the solver's focus from quantity to quality. Whether by stripping literals via in-processing (Luo et al.), factoring structures (Yan et al.), or computing minimal sub-assignments via MaxSAT (Oliveras et al.), reducing redundancy ensures that every single clause in the formula exerts maximum pruning pressure on the search space.
Key Foundational Work
Accelerating SAT Solving by Common Subclause Elimination (2015) — contributed 8 concept elements to this direction.
Redundancy in Random SAT Formulas (2000) — contributed 2 concept elements to this direction.