Parallel Beam Search for Combinatorial Optimization (Extended Abstract)

Authors

  • Nikolaus Frohner Institute of Logic and Computation, TU Wien
  • Jan Gmys University of Lille, Inria Lille - Nord Europe, BONUS
  • Nouredine Melab University of Lille, Inria Lille - Nord Europe, BONUS
  • Günther R. Raidl Institute of Logic and Computation, TU Wien
  • El-ghazali Talbi University of Lille, Inria Lille - Nord Europe, BONUS

Keywords:

Combinatorial Optimization

Abstract

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.

Downloads

Published

2022-07-17