Parallel Beam Search for Combinatorial ...
Document type :
Communication dans un congrès avec actes
Title :
Parallel Beam Search for Combinatorial Optimization
Author(s) :
Frohner, Nikolaus [Auteur]
Vienna University of Technology = Technische Universität Wien [TU Wien]
Gmys, Jan [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Melab, Nouredine [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Raidl, Günter [Auteur]
Vienna University of Technology = Technische Universität Wien [TU Wien]
Talbi, El-Ghazali [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Vienna University of Technology = Technische Universität Wien [TU Wien]
Gmys, Jan [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Melab, Nouredine [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Raidl, Günter [Auteur]
Vienna University of Technology = Technische Universität Wien [TU Wien]
Talbi, El-Ghazali [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Conference title :
International Workshop on Parallel and Distributed Algorithms and Decision Sciences (PDADS 2022)
City :
Bordeaux
Country :
France
Start date of the conference :
2022-08-29
HAL domain(s) :
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
Informatique [cs]/Algorithme et structure de données [cs.DS]
Computer Science [cs]/Operations Research [math.OC]
Informatique [cs]/Algorithme et structure de données [cs.DS]
Computer Science [cs]/Operations Research [math.OC]
English abstract : [en]
Inspired by the recent success of parallelized exact methods to solve difficult scheduling problems, we present a general parallel beam search framework for combinatorial optimization problems. Beam search is a constructive ...
Show more >Inspired by the recent success of parallelized exact methods to solve difficult scheduling problems, we present 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. Diversification and inter-node parallelization are combined by performing multiple randomized runs on independent workers communicating via MPI. For sufficiently large problem instances and beam widths our pro-totypical implementation in the JIT-compiled Julia language admits speed-ups between 30 − 42× on 46 cores with uniform memory access for two difficult classical problems, namely Permutation Flow Shop Scheduling (PFSP) with flowtime objective and the Traveling Tournament Problem (TTP). This allowed us to perform large beam width runs to find 11 new best feasible solutions for 22 difficult TTP benchmark instances up to 20 teams with an average wallclock runtime of about one hour per instance.Show less >
Show more >Inspired by the recent success of parallelized exact methods to solve difficult scheduling problems, we present 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. Diversification and inter-node parallelization are combined by performing multiple randomized runs on independent workers communicating via MPI. For sufficiently large problem instances and beam widths our pro-totypical implementation in the JIT-compiled Julia language admits speed-ups between 30 − 42× on 46 cores with uniform memory access for two difficult classical problems, namely Permutation Flow Shop Scheduling (PFSP) with flowtime objective and the Traveling Tournament Problem (TTP). This allowed us to perform large beam width runs to find 11 new best feasible solutions for 22 difficult TTP benchmark instances up to 20 teams with an average wallclock runtime of about one hour per instance.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
Source :