Parallel Beam Search Algorithms for Domain-Independent Dynamic Programming
Authors: Ryo Kuroiwa, J. Christopher Beck
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The experimental results show that our solvers achieve significant speedup and performance improvement compared to CABS and find the new best solutions for two instances of the traveling salesperson problem with time windows. In addition, our solvers outperform multi-thread MIP and CP solvers in four of six combinatorial optimization problems tested. |
| Researcher Affiliation | Academia | Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Canada, ON M5S 3G8 ryo.kuroiwa@mail.utoronto.ca, jcb@mie.utoronto.ca |
| Pseudocode | Yes | Algorithm 1: Beam search. Algorithm 2: Insert a successor to a set if it is not dominated. Algorithm 3: Shared beam search (SBS). Algorithm 4: Hash distributed beam search 1 (HDBS1). Algorithm 5: Receive states from a channel. Algorithm 6: Aggregate information of the current layer. Algorithm 7: Hash distributed beam search 2 (HDBS2). Algorithm 8: Receive the information of the previous layer. |
| Open Source Code | Yes | We implement multi-thread DIDP solvers using CABS with SBS (CASBS), HDBS1 (CAHDBS1), and HDBS2 (CAHDBS2) in an existing DIDP framework, didp-rs,7 with Rust 1.65.0. 7https://github.com/domain-independent-dp/didp-rs/releases/ tag/parallel-aaai24 |
| Open Datasets | No | The paper mentions using specific problems like TSPTW, CVRP, SALBP-1, etc., and refers to Dy PDL models from Kuroiwa and Beck (2023c) and MIP/CP models from Kuroiwa and Beck (2023b), but does not explicitly provide access details or specify public availability for the datasets used in the experiments. |
| Dataset Splits | No | The paper does not explicitly specify training, validation, and test splits (e.g., percentages, counts, or explicit references to predefined splits). |
| Hardware Specification | Yes | All experiments are run on a machine with 2 Intel Xeon Gold 6148 CPUs (40 cores in total) using 188 GB memory and 300 seconds. |
| Software Dependencies | Yes | We implement multi-thread DIDP solvers using CABS with SBS (CASBS), HDBS1 (CAHDBS1), and HDBS2 (CAHDBS2) in an existing DIDP framework, didp-rs,7 with Rust 1.65.0. We use Dash Map 5.4.0. We use Rayon 1.7.0. We use Fx Hash from rustc-hash 1.1.0. For message passing, we use Crossbeam Channel 0.5.8. For broadcast in HDBS1, we use bus 2.4.0. We also evaluate MIP and CP models using Gurobi 10.0.1 and IBM ILOG CP Optimizer 22.1.0. We use the Dy PDL models from Kuroiwa and Beck (2023c) and MIP and CP models from Kuroiwa and Beck (2023b)8 with Python 3.11.2. For a memory allocator, jemalloc 5.2.19 is used. |
| Experiment Setup | Yes | We use up to 32 threads, and CABS starts from b = 32. With k threads, we use m = 4k shards, following the default of Dash Map. For a memory allocator, jemalloc 5.2.19 is used. All experiments are run on a machine with 2 Intel Xeon Gold 6148 CPUs (40 cores in total) using 188 GB memory and 300 seconds. |