Search Space Pruning via Logical Preprocessing

31 concepts23 papers

When solving hard combinatorial problems—whether Boolean Satisfiability (SAT), automated planning, or first-order theorem proving—solvers face the dreaded challenge of combinatorial explosion. As the number of variables or clauses grows, the search space expands exponentially. A naive solver spends most of its computational budget exploring dead ends: branches of the search tree that were doomed from the start due to implicit constraints.

The core insight of logical preprocessing is that we can use cheap, incomplete inference methods to uncover these hidden constraints before the main search begins. Instead of letting a heavy-duty heuristic search engine stumble through a massive, highly constrained space, preprocessing drastically reduces the dimensionality of the problem upfront.

The Power of Cheap Inference: Unit Propagation and Variable Fixing

How do we prune a search space without actually searching? The answer lies in executing deterministic inference rules that guarantee correctness without branching. The most prominent examples are unit propagation and binary resolution. If a formula contains a clause with only a single unresolved literal (a unit clause), that literal's truth value is completely forced. Propagating this choice simplifies other clauses, often triggering a cascade of further variable assignments.

Anbulagan et al. demonstrated the power of this synergy by using resolution as a preprocessing step for Stochastic Local Search (SLS) solvers in Old Resolution Meets Modern SLS. SLS solvers excel at navigating smooth local search spaces but easily get trapped by highly structured, brittle constraints. By using unit propagation to fix the truth values of deterministic variables beforehand, the authors reduced the dimensionality of the active search space, turning complex structured problems into nearly trivial tasks for the local search engine.

[Original Problem Space] ──► [Logical Preprocessing] ──► [Reduced Problem Space] ──► [Local Search Solver]
  (Massive, Brittle)          (Unit Propagation /          (Fewer Active Variables)     (Fast Convergence)
                              Binary Resolution)

Similarly, Brafman showed in Reachability, Relevance, Resolution and the Planning as Satisfiability Approach that standard SAT solvers often fail to "see" reachability and relevance constraints in automated planning. By introducing a binary resolution preprocessing step—which resolves pairs of binary clauses to derive unit clauses—hidden structural shortcuts are brought to light, yielding massive speedups.

This concept extends directly to industrial combinatorial problems. In the context of the Latin Square Completion problem, Pan et al. in A Fast Local Search Algorithm for the Latin Square Completion Problem and Xie et al. in A Swap Relaxation-Based Local Search for the Latin Square Completion Problem applied logical reduction rules to fix deterministic cell values before engaging heuristics. By locking in cells that have only one valid symbol, the preprocessing phase solves large portions of the problem instance upfront. This allows subsequent local search heuristics to focus entirely on the most complex, unresolved constraints. A similar pre-solving optimization is leveraged by Dumancic et al. in Automated Reasoning and Learning for Automated Payroll Management, where fixing known input variables and propagating them through a complex rule set significantly decreases the number of active constraints that the solver must process.

Taming Resolution: Ordered Literals and Simplification Orderings

In first-order logic and automated theorem proving, the challenge is not just fixing boolean variables, but managing the explosion of generated clauses during resolution. If every clause can resolve with every other clause, the prover quickly drowns in irrelevant data. To prevent this, researchers introduce strict orderings on literals and terms to restrict where and how inferences can occur. The intuition is simple: only allow resolution steps that reduce the complexity of the clause or focus on its "largest" components.

Darlington pioneered this with ordered literal resolution in Theorem Provers as Question Answerers, prioritizing the resolution of specific parts of a logical clause based on predefined selection rules. By constraining the solver to focus only on a designated literal, the number of possible resolution steps drops dramatically.

This idea was refined by Hsiang et al. in Complete Inference Rules for the Cancellation Laws and the authors of 86), who integrated inference rules with ground-linear simplification orderings. By ranking terms by complexity and restricting rule applications strictly to the lexicographically largest or most complex literals, the theorem prover avoids redundant or circular steps that do not progress toward the goal.

Without Ordering:  [Clause A] can resolve with [Clause B, C, D, E...] ──► Combinatorial Explosion
With Ordering:     [Clause A] restricted to its Maximal Literal       ──► Linear/Pruned Search Tree

Similarly, Dershowitz utilized term orderings for equational Horn clauses in Ordering-Based Strategies for Horn Clauses, prioritizing positive literals over negative ones to constrain the direction of inferences. By limiting substitutions to the maximal terms of equations, the search space is pruned by systematically forcing a reduction in term complexity. In the same vein, Chu et al. introduced Rough Resolution in Rough Resolution: A Refinement of Resolution to Remove Large Literals to eliminate complex, "large" literals early in the proof process, preventing instance-based theorem provers from experiencing a combinatorial explosion of irrelevant data. To systematically control the model-finding process, the authors of Ordered Semantic Hyper Linking likewise imposed orderings on ground literals and interpretations to manage the search space effectively.

Exposing Hidden Structure: Global Rules and Failed Literals

Beyond local clause resolution, preprocessing can leverage global structural properties of a problem to eliminate variables. One powerful technique is the failed literal rule. As explored by Kautz et al. in the Blackbox planning system (Unifying SAT-based and Graph-based Planning), this rule tentatively sets a literal to true and runs a quick pass of unit propagation. If this assumption leads to an immediate contradiction, the literal must be false in any valid solution. This limited lookahead prunes propositional formulas before the main search phase even begins.

The analytical foundation for why these structural rules work so well was mapped out by Purdom et al. in Evaluating Search Methods Analytically. By evaluating search methods analytically, the authors showed that identifying literals appearing in only one polarity or eliminating variables that do not affect the outcome directly targets sparse variable interactions, shifting runtimes from exponential to polynomial.

When problems possess rich domain-specific structures, these reduction rules become even more potent:

Why It Works: The Intuition

Why does inference-as-preprocessing work so universally across SAT, planning, and theorem proving? Because search algorithms are fundamentally blind; they rely on heuristics to guess the next step.

Preprocessing acts as a non-backtracking filter. By spending a small, polynomial amount of computational effort upfront to propagate constraints, order literals, or eliminate failed variables, we alter the topology of the search space. We cut off entire subtrees of dead ends before the solver ever has a chance to wander into them, ensuring that the heavy-duty search phase is focused entirely on the core combinatorial core of the problem.

Key Foundational Work

Theorem Provers as Question Answerers (1969) — contributed 1 concept elements to this direction.
The Efficacy of RUE Resolution Experimental Results and Heuristic Theory (1981) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_constraint_based_pre_processing_44b97fee,
  title = {constraint-based pre-processing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constraint-based-pre-processing/rdr_44b97fee0f4b42c99ac94e294d5993d0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_constraint_based_pre_processing_44b97fee_v1,
  title = {constraint-based pre-processing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constraint-based-pre-processing/rdr_44b97fee0f4b42c99ac94e294d5993d0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake