Show simple item record

Parallélisation de métaheuristiques hybrides pour la résolution de POC

dc.contributorParis Sciences et Lettres
dc.contributor.advisorMahjoub, Ali Ridha
dc.contributor.advisorMahjoub, Zaher
hal.structure.identifier
dc.contributor.authorLabidi, Mohamed Khalil*
dc.date.accessioned2019-02-19T13:53:18Z
dc.date.available2019-02-19T13:53:18Z
dc.date.issued2018-09-20
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18460
dc.description.abstractfrL’Optimisation Combinatoire (OC) est un domaine de recherche qui est en perpétuel changement. Résoudre un problème d’optimisation combinatoire (POC) consiste essentiellement à trouver la ou les meilleures solutions dans un ensemble des solutions réalisables appelé espace de recherche qui est généralement de cardinalité exponentielle en la taille du problème. Pour résoudre des POC, plusieurs méthodes ont été proposées dans la littérature. On distingue principalement les méthodes exactes et les méthodes d’approximation. Ne pouvant pas viser une résolution exacte de problèmes NP-Complets lorsque la taille du problème dépasse une certain seuil, les chercheurs on eu de plus en plus recours, depuis quelques décennies, aux algorithmes dits hybrides (AH) ou encore à au calcul parallèle. Dans cette thèse, nous considérons la classe POC des problèmes de conception d'un réseau fiable. Nous présentons un algorithme hybride parallèle d'approximation basé sur un algorithme glouton, un algorithme de relaxation Lagrangienne et un algorithme génétique, qui produit des bornes inférieure et supérieure pour les formulations à base de flows. Afin de valider l'approche proposée, une série d'expérimentations est menée sur plusieurs applications: le Problème de conception d'un réseau k-arête-connexe avec contrainte de borne (kHNDP) avec L=2,3, le problème de conception d'un réseau fiable Steiner k-arête-connexe (SkESNDP) et ensuite deux problèmes plus généraux, à savoir le kHNDP avec L >= 2 et le problème de conception d'un réseau fiable k-arête-connexe (kESNDP). L'étude expérimentale de la parallélisation est présentée après cela. Dans la dernière partie de ce travail, nous présentons deux algorithmes parallèles exactes: un Branch-and-Bound distribué et un Branch-and-Cut distribué. Une série d'expérimentation a été menée sur une grappe de 128 processeurs, et des accélération intéressantes ont été atteintes pour la résolution du problèmes kHNDP avec k=3 et L=3.fr
dc.language.isoen
dc.subjectCalcul parallèlefr
dc.subjectMétaheuristiquefr
dc.subjectOptimisation Combinatoirefr
dc.subjectAlgorithme de coupes et branchementsfr
dc.subjectHybridationfr
dc.subjectConception de réseauxfr
dc.subjectAlgorithme de séparation et évaluationfr
dc.subjectParallel computingen
dc.subjectMetaheuristicen
dc.subjectCombinatorial Optimizationen
dc.subjectBranch-And-Cut algorithmen
dc.subjectHybridizationen
dc.subjectNetwork Designen
dc.subjectBranch-And-Bound algorithmen
dc.subject.ddc004
dc.titleParallelisation of hybrid metaheuristics for COP solvingen
dc.titleParallélisation de métaheuristiques hybrides pour la résolution de POCfr
dc.typeThèse
dc.contributor.editoruniversityUniversité Paris Dauphine
dc.contributor.editoruniversityotherUniversité de Tunis El-Manar
dc.description.abstractenCombinatorial Optimization (CO) is an area of research that is in a constant progress. Solving a Combinatorial Optimization Problem (COP) consists essentially in finding the best solution (s) in a set of feasible solutions called a search space that is usually exponential in cardinality in the size of the problem. To solve COPs, several methods have been proposed in the literature. A distinction is made mainly between exact methods and approximation methods. Since it is not possible to aim for an exact resolution of NP-Complete problems when the size of the problem exceeds a certain threshold, researchers have increasingly used Hybrid (HA) or parallel computing algorithms in recent decades. In this thesis we consider the COP class of Survivability Network Design Problems. We present an approximation parallel hybrid algorithm based on a greedy algorithm, a Lagrangian relaxation algorithm and a genetic algorithm which produces both lower and upper bounds for flow-based formulations. In order to validate the proposed approach, a series of experiments is carried out on several applications: the k-Edge-Connected Hop-Constrained Network Design Problem (kHNDP) when L = 2,3, The problem of the Steiner k-Edge-Connected Network Design Problem (SkESNDP) and then, two more general problems namely the kHNDP when L >= 2 and the k-Edge-Connected Network Design Problem (kESNDP). The experimental study of the parallelisation is presented after that. In the last part of this work, we present a two parallel exact algorithms: a distributed Branch-and-Bound and a distributed Branch-and-Cut. A series of experiments has been made on a cluster of 128 processors and interesting speedups has been reached in kHNDP resolution when k=3 and L=3.en
dc.identifier.theseid2018PSLED029
dc.subject.ddclabelInformatique générale
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record