Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning Branching Heuristics for Propositional Model Counting
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 SharpSAT's VSADS branching heuristic with a problem-family-trained GNN policy | SharpSAT · I.I.D. test instances across the reported problem families | branching steps: 220 -> 195; 466 -> 261; 52 -> 24; 86 -> 30; 370 -> 184; 353 -> 198; 338 -> 206; 195 -> 66; 328 -> 205; 412 -> 266 | Helped |
| Apply the learned branching heuristic without further training on larger instances | NeuroSharp · Grid planning [10,12] | branching steps: 93,093 -> 1,320 | Helped |
| Apply the learned branching heuristic without further training on larger instances | NeuroSharp · Cellular automaton [35,192,128] | branching steps: 21,166 -> 1,668 | Helped |
| Add the time-step feature to the policy input (ablation) | NeuroSharp on grid planning · Grid planning [10,12] | branching steps | Helped |
| Use only the time-step feature, without computing variable embeddings (ablation) | NeuroSharp on grid planning · Grid planning [10,12] | branching steps | Helped |
| Add VSADS variable scores as model features (ablation) | NeuroSharp · Cellular automaton [49,256,200] | branching steps | Hurt |
| Add VSADS variable scores as model features (ablation) | NeuroSharp · Grid planning [10,12] | branching steps | Hurt |
| Increase GNN message-passing iterations beyond 2 (ablation) | NeuroSharp · I.I.D. generalization | branching steps | Hurt |
| Change among the tested GNN architectures (ablation) | NeuroSharp · I.I.D. generalization | branching steps | No clear effect |
Closest papers by meaning
- Model Counting and Sampling via Semiring Extensions (AAAI 2024 · similarity 0.88)
- The Gradient of Algebraic Model Counting (AAAI 2025 · similarity 0.87)
- Learning Better Representations From Less Data For Propositional Satisfiability (NeurIPS 2024 · similarity 0.87)
- Engineering an Exact Pseudo-Boolean Model Counter (AAAI 2024 · similarity 0.87)
- SAT-Based Tree Decomposition with Iterative Cascading Policy Selection (AAAI 2024 · similarity 0.86)
- Learning How to Cube (NeurIPS 2026 · 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.