Learned SAT Preprocessing for Faster Solving

ISEF Category: Systems Software

Subcategory: Algorithms  ·  Difficulty: Advanced  ·  Setup: University Lab  ·  Time: Full Year

The Hook

A SAT solver can spend hours on a problem that looks tiny on paper. The difference often comes down to which clauses stay and which ones get removed first. That makes preprocessing a great place for a smart heuristic. If you like code and puzzles, this topic lets you study how a small model can speed up a real solver without touching its core.

What Is It?

SAT means satisfiability. A SAT solver tries to decide whether a set of logic clauses can all be true at once. SMT adds extra theories, like arithmetic or bit-vectors, on top of that logic layer. Think of the solver as a huge maze search, and preprocessing as the person who clears dead ends before the search starts.

Clause deletion heuristics decide which clauses to keep and which to remove or weaken before the solver runs. Solver telemetry means the clues the solver leaves behind while it works, such as conflict counts, variable activity, or propagation patterns. A tiny graph neural network, or GNN, can read the clause-variable graph and predict which clauses look unhelpful. Your project studies whether those predictions reduce wall-clock time on benchmark sets without changing the solver's final answer.

Why This Is a Good Topic

This makes a strong science fair topic because you can test a clear input and output, then compare a baseline solver run against a learned preprocessing version. You also get a real systems problem, since faster SAT and SMT solving matters in hardware design, verification, scheduling, and formal methods. A student can learn graph representation, feature engineering, model evaluation, and benchmarking. The project can start small, then grow into a deeper study if your results look promising.

Research Questions

• How does a learned clause-deletion heuristic compare with a fixed baseline heuristic on SAT benchmark solve time?
• What is the effect of adding solver telemetry features on the accuracy of clause usefulness predictions?
• Does a tiny GNN improve preprocessing decisions more than hand-built graph features alone?
• To what extent does the heuristic transfer across different benchmark families, such as industrial and crafted instances?
• Which clause graph features best predict whether a clause should stay or go?
• How does preprocessing change the number of conflicts, propagations, and total runtime in the underlying solver?
• What is the effect of training on SAT instances and testing on SMT-inspired encodings?

Basic Materials

• Laptop or desktop computer with a modern CPU.
• Linux environment or Windows Subsystem for Linux.
• Open-source SAT solver with preprocessing support.
• Small SAT or SMT benchmark set from public competition archives.
• Python 3 with NumPy and pandas.
• NetworkX for graph feature extraction.
• Matplotlib or Seaborn for plots.
• Git for version control.
• Spreadsheet software for tracking runs and metadata.

Advanced Materials

• Workstation or lab computer with multiple CPU cores.
• Access to large SAT-Competition or SMT-LIB benchmark collections.
• Open-source SAT solver source code for instrumentation.
• Python with PyTorch or PyTorch Geometric.
• C++ compiler toolchain.
• Performance profiling tools such as perf or Valgrind.
• Apache Arrow or Parquet storage for large run logs.
• JupyterLab or VS Code for analysis notebooks.

Software & Tools

• Python: Runs feature extraction, training, and result analysis scripts.
• PyTorch: Trains the tiny GNN on clause and telemetry data.
• NetworkX: Builds clause-variable graphs and computes structural features.
• ImageJ: Not used for this topic, so skip it unless you need image-based figures for a poster.
• GitHub Desktop: Tracks code changes and benchmark experiments in a clean history.

Experiment Steps

1. Define the solver decision point you want to improve, such as clause removal before search begins.
2. Choose the benchmark families you will test, and separate training, validation, and holdout sets.
3. Encode each formula as a graph and select telemetry features that the model can read.
4. Set up a baseline heuristic so you can compare the learned method against a simple rule.
5. Plan evaluation metrics that include runtime, solved count, conflicts, and preprocessing overhead.
6. Design ablation tests that remove one feature group at a time to see what actually matters.

Common Pitfalls

• Training on the same benchmark family you use for testing, which makes the model look better than it is.
• Measuring only solved count and ignoring preprocessing cost, which can hide a slower overall pipeline.
• Feeding the GNN features that leak future solver information, which breaks the validity of the comparison.
• Comparing runs with different CPU settings or solver flags, which makes timing data noisy.
• Using too few benchmarks, which makes results swing wildly from one instance set to the next.

What Makes This Competitive

A strong version of this project does more than report a speedup. You need clean baselines, a fair benchmark split, and ablation tests that show why the model helps. Strong entries also test transfer across multiple instance families and report both runtime and solver-behavior metrics. If you can explain when the heuristic fails, your work looks much more like real research.

Project Variations

• Test whether the same learned heuristic works on only industrial SAT instances, then compare it with crafted instances.
• Replace the tiny GNN with a simpler graph model, then measure whether the extra complexity really helps.
• Focus on solver telemetry from one stage only, such as conflicts or propagation counts, and see which signal carries the most predictive power.

Learn More

• SAT Competition: Search for benchmark archives, solver tracks, and instance categories used in modern SAT research.
• SMT-LIB: Find public SMT benchmark families and background material on satisfiability modulo theories.
• MIT OpenCourseWare: Search for algorithms, graph theory, and machine learning courses that support the graph and optimization parts of this topic.
• PubMed: Search for review articles on graph neural networks if you want a broad model-design overview, even though this topic is in computer science.
• arXiv: Search for recent preprints on learned SAT solving, clause learning, and preprocessing heuristics.