Research map / Learning theory and algorithms / Combinatorial and search optimization
Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation
Daniel Anderson, Gregor Hendel, Pierre Le Bodic, Merlin Viernickel
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| add acceleration to windowed velocity estimate (ablation) | tree-size estimate · large trees, median error | percentage error: 187% -> 48% | Improved |
| add acceleration to windowed velocity estimate (ablation) | tree-size estimate · all instances, median error | percentage error: 14% -> 13% | Improved |
| add acceleration without a window (ablation) | tree-size estimate · large trees, median error | percentage error: 43% -> 49% | Hurt |
| add acceleration without a window (ablation) | tree-size estimate · all instances, median error | percentage error: 16% -> 21% | Hurt |
| use moving window instead of no window (with acceleration) (ablation) | tree-size estimate · all instances, median error | percentage error: 21% -> 13% | Improved |
| use domain-based probabilities pk instead of uniform pu (ablation) | progress measure · all instances | average error: 0.17 -> 0.16 | No clear effect |
| clairvoyant restart with window-acc instead of SCIP default | SCIP 6.0 · ALL (490) | solving time T: 183.1 -> 175.6 | Improved |
| clairvoyant restart with window-acc instead of SCIP default | SCIP 6.0 · GE1000 (64) | solving time T: 2 088.7 -> 1 869.9 | Improved |
| window-vel instead of default | SCIP 6.0 · ALL (490) | solving time T: 183.1 -> 178.2 | Improved |
| linear forecast restart instead of default | SCIP 6.0 · GE1000 (64) | solving time T: 2 088.7 -> 2 319.9 | Hurt |
| disable restarts (0-restart) vs default | SCIP 6.0 · ALL (490) | solving time T: 183.1 -> 179.5 | Improved |
| allow one root restart (1-restart) vs default | SCIP 6.0 · ALL (490) | solving time T: 183.1 -> 183.3 | No clear effect |
Closest papers by meaning
- Finding Good Partial Assignments during Restart-Based Branch and Bound Search (AAAI 2023 · similarity 0.84)
- Learning to Branch in Mixed Integer Programming (AAAI 2016 · similarity 0.84)
- SMART: When is it Actually Worth Expanding a Speculative Tree? (ECCV 2026 · similarity 0.84)
- Search Strategy Generation for Branch and Bound Using Genetic Programming (AAAI 2025 · similarity 0.83)
- ZetaEvolve: Learning to Search through History-Conditioned Potential Value (NeurIPS 2026 · similarity 0.83)
- Eco Search: A No-delay Best-First Search Algorithm for Program Synthesis (AAAI 2025 · similarity 0.82)
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.
