Parallel Beam Search for Combinatorial Optimization (Extended Abstract)
| Autor: | Nikolaus Frohner, Jan Gmys, Nouredine Melab, Günther R. Raidl, El-ghazali Talbi |
|---|---|
| Rok vydání: | 2022 |
| Zdroj: | Proceedings of the International Symposium on Combinatorial Search. 15:273-275 |
| ISSN: | 2832-9163 2832-9171 |
| DOI: | 10.1609/socs.v15i1.21783 |
| Popis: | Inspired by the recent success of parallelized exact methods to solve difficult scheduling problems, we present preliminary results of a general parallel beam search framework for combinatorial optimization problems. Beam search is a constructive metaheuristic traversing a search tree layer by layer while keeping in each layer a bounded number of promising nodes to consider many partial solutions in parallel. We propose a variant which is suitable for intra-node parallelization by multithreading with data parallelism. For sufficiently large problem instances and beam widths our work-in-progress implementation in the JIT-compiled Julia language admits promising speed-ups over 30x on 32 cores with uniform memory access for the Permutation Flow Shop Scheduling (PFSP) problem with flowtime objective. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|