Research map / Learning theory and algorithms / Combinatorial and search optimization
Parallel Beam Search Algorithms for Domain-Independent Dynamic Programming
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes three parallel beam search algorithms (shared beam search and two hash distributed beam search variants) for multi-threaded complete anytime beam search in domain-independent dynamic programming, achieving 9-39x speedup with 32 threads.
Problem
Current domain-independent dynamic programming (DIDP) solvers based on beam search cannot use multiple threads, unlike state-of-the-art MIP and CP solvers.
Approach
Parallelizes complete anytime beam search (CABS) with a shared concurrent hash table for dominance checking (SBS), and with hash-based state distribution and message passing across workers in two synchronization variants (HDBS1, HDBS2) adapted from parallel best-first search.
Key results
- With 32 threads, parallel DIDP solvers achieve 9 to 39 times speedup on average over sequential CABS (CAHDBS2 TSPTW speedup 13.8, MOSP 9.1, graph-clear 10.5).
- CAHDBS1 and CAHDBS2 find new best solutions for rbg193.2.tw (12138) and rbg233.2.tw (14492) in TSPTW.
- Parallel DIDP solvers outperform multi-thread MIP and CP in four of six tested problems.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| parallelize CABS with shared beam search using 32 threads | CABS · TSPTW | speedup: 9.5 | Helped |
| parallelize CABS with hash distributed beam search 1 using 32 threads | CABS · TSPTW | speedup: 13.0 | Helped |
| parallelize CABS with hash distributed beam search 2 using 32 threads | CABS · TSPTW | speedup: 13.3 | Helped |
| parallelize CABS with hash distributed beam search 1 using 32 threads | CABS · CVRP | coverage: 5 -> 9 | Helped |
| parallelize CABS with hash distributed beam search 2 using 32 threads | CABS · CVRP | speedup: 9.3 | Helped |
| parallelize CABS with hash distributed beam search 1 using 32 threads | CABS · SALBP-1 | speedup: 16.7 | Helped |
| parallelize CABS with hash distributed beam search 2 using 32 threads | CABS · SALBP-1 | speedup: 18.8 | Helped |
| parallelize CABS with shared beam search using 32 threads | CABS · Bin Packing | coverage: 1110 -> 1077 | Hurt |
| parallelize CABS with hash distributed beam search 1 using 32 threads | CABS · Bin Packing | coverage: 1110 -> 1239 | Helped |
| parallelize CABS with hash distributed beam search 2 using 32 threads | CABS · Bin Packing | speedup: 39.6 | Helped |
| parallelize CABS with hash distributed beam search 1 using 32 threads | CABS · MOSP | speedup: 8.9 | Helped |
| parallelize CABS with hash distributed beam search 2 using 32 threads | CABS · Graph-Clear | speedup: 10.3 | Helped |
Surprising findings
- In SALBP-1 and bin packing, HDBS shows super-linear speedup because parallel search changes the beam search behavior and finds good solutions sooner.
- Shared beam search (CASBS) solves fewer instances than sequential CABS in bin packing.
Limitations
- Frequent inter-thread communication may be a bottleneck for HDBS.
- Parallelization changes beam search behavior, so speedup differs from speedup per expansion in some problems (e.g., SALBP-1, bin packing).
- Abstracted hash functions tailored to DIDP are not yet designed.
Experimental setup
Datasets: TSPTW CVRP SALBP-1 bin packing MOSP graph-clear
Benchmarks: TSPTW CVRP SALBP-1 bin packing MOSP graph-clear
Metrics: coverage speedup primal gap primal integral expansion ratio
Baselines: CABS (sequential) MIP (Gurobi) CP (IBM ILOG CP Optimizer) CASBS with 1 thread
Builds on: complete anytime beam search domain-independent dynamic programming parallel best-first search DashMap
Closest papers by meaning
- Learning to Schedule Heuristics in Branch and Bound (NeurIPS 2021 · similarity 0.85)
- Parameterized Algorithms for MILPs with Small Treedepth (AAAI 2021 · similarity 0.84)
- Rectangle Search: An Anytime Beam Search (AAAI 2024 · similarity 0.83)
- DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem (AAAI 2025 · similarity 0.83)
- MILP-StuDio: MILP Instance Generation via Block Structure Decomposition (NeurIPS 2024 · similarity 0.82)
- Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation (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.