Parallel Beam Search for Combinatorial ...
Type de document :
Communication dans un congrès avec actes
Titre :
Parallel Beam Search for Combinatorial Optimization
Auteur(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]
Titre de la manifestation scientifique :
International Workshop on Parallel and Distributed Algorithms and Decision Sciences (PDADS 2022)
Ville :
Bordeaux
Pays :
France
Date de début de la manifestation scientifique :
2022-08-29
Discipline(s) HAL :
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]
Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :