Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning Local Search Heuristics for Boolean Satisfiability
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace WalkSAT heuristic with class-specialized GNN variable selection | local search SAT · clique3(20, 0.05) | average steps: 237 -> 116 | Helped |
| replace WalkSAT heuristic with class-specialized GNN variable selection | local search SAT · rand3(50, 213) | average steps: 385 -> 367 | Helped |
| replace WalkSAT with learned heuristic | local search SAT · domset4(12, 0.2) | average steps: 217 -> 205 | No clear effect |
| evaluate heuristic on a problem class different from its training class (ablation) | learned heuristic · clique3(20, 0.05) | average steps: 116 -> 529 | Hurt |
| train on generic SR(10) distribution instead of rand3(10,43) (ablation) | learned heuristic · clique3(10, 0.1) | average steps: 649 -> 363 | Helped |
| curriculum over increasing problem sizes (ablation) | REINFORCE training · training curves | steps | Helped |
| evaluate on random graph families unseen in training | learned heuristic · cliquek/coverk/colork | average steps vs WalkSAT: clique 198 vs 285; domset 271 vs 255 | Mixed |
| increase maximum iterations for SR(10) heuristic on larger SR(n) | learned heuristic · SR(n) large | percentage solved | Helped |
Closest papers by meaning
- Can Q-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver? (NeurIPS 2020 · similarity 0.92)
- Learning from Algorithm Feedback: One-Shot SAT Solver Guidance with GNNs (ICLR 2026 · similarity 0.91)
- On the Expressive Power of GNNs for Boolean Satisfiability (ICLR 2026 · similarity 0.90)
- Learning Splitting Heuristics in Divide-and-Conquer SAT Solvers with Reinforcement Learning (ICLR 2025 · similarity 0.89)
- Learning How to Cube (NeurIPS 2026 · similarity 0.89)
- HardCore Generation: Generating Hard UNSAT Problems for Data Augmentation (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.