Research map / Learning theory and algorithms / Combinatorial and search optimization
Finding Good Partial Assignments during Restart-Based Branch and Bound Search
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 |
|---|---|---|---|
| Use GPA partial assignments extracted from intermediate solutions | Restart-based BBS with ABS, SBPS, and BIVS · MiniZinc benchmarks, 7200s | better-solution comparisons against baseline (wins:losses): 84:43 | Helped |
| Use RGPA partial assignments, ranked by average contribution scores | Restart-based BBS with ABS, SBPS, and BIVS · MiniZinc benchmarks, 7200s | better-solution comparisons against baseline (wins:losses): 84:40 | Helped |
| Use GPA partial assignments at restarts | Restart-based BBS · MiniZinc benchmarks, 7200s | completed instances: 269 -> 276 | Helped |
| Use RGPA partial assignments at restarts | Restart-based BBS · MiniZinc benchmarks, 7200s | completed instances: 269 -> 275 | Helped |
| Use ABS variable selection instead of dom/wdeg | SBPS with BIVS value selection · MiniZinc benchmark instances | better-solution comparisons (wins:losses): 174:54 | Helped |
| Set the RGPA solution-queue maximum to 20 rather than 10 (ablation) | RGPA · MiniZinc benchmarks | better-solution comparisons (wins:losses): 41:38 | Helped |
| Set the RGPA solution-queue maximum to 30 rather than 20 (ablation) | RGPA · MiniZinc benchmarks | better-solution comparisons (wins:losses): 24:30 | Hurt |
| Set the RGPA solution-queue maximum to 50 rather than 20 (ablation) | RGPA · MiniZinc benchmarks | better-solution comparisons (wins:losses): 20:32 | Hurt |
| Remove the maximum on the RGPA solution queue rather than using m=20 (ablation) | RGPA · MiniZinc benchmarks | better-solution comparisons (wins:losses): 19:32 | Hurt |
| Add the temporary restart cutoff to RGPA with resetting restart sequence (ablation) | RGPA(D) · MiniZinc benchmarks | better-solution comparisons (wins:losses): 70:50 | Helped |
| Use RGPA rather than FPMS | OpenStacks · OpenStacks | average objective: 11.73 -> 10.5 | Helped |
| Use RGPA rather than FPMS | Trucking · Trucking | average objective: 1771 -> 470 | Helped |
Closest papers by meaning
- Counting-Based Search for Constraint Optimization Problems (AAAI 2016 · similarity 0.87)
- Search Strategy Generation for Branch and Bound Using Genetic Programming (AAAI 2025 · similarity 0.87)
- Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies (AAAI 2021 · similarity 0.86)
- GDBA Revisited: Unleashing the Power of Guided Local Search for Distributed Constraint Optimization (AAAI 2026 · similarity 0.85)
- Necessary and Sufficient Conditions for Avoiding Reopenings in Best First Suboptimal Search with General Bounding Functions (AAAI 2021 · similarity 0.85)
- Look-Ahead with Mini-Bucket Heuristics for MPE (AAAI 2016 · similarity 0.84)
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.