LogoLogo

Lalami, Mohamed Esseghir. Contribution à la résolution de problèmes d'optimisation combinatoire : méthodes séquentielles et parallèles

Lalami, Mohamed Esseghir (2012). Contribution à la résolution de problèmes d'optimisation combinatoire : méthodes séquentielles et parallèles.

[img]
Preview
PDF - nécessite un logiciel de visualisation PDF comme GSview, Xpdf or Adobe Acrobat Reader
1529Kb

Résumé en francais

Les problèmes d'optimisation combinatoire sont souvent des problèmes très difficiles dont la résolution par des méthodes exactes peut s'avérer très longue ou peu réaliste. L'utilisation de méthodes heuristiques permet d'obtenir des solutions de bonne qualité en un temps de résolution raisonnable. Les heuristiques sont aussi très utiles pour le développement de méthodes exactes fondées sur des techniques d'évaluation et de séparation. Nous nous sommes intéressés dans un premier temps à proposer une méthode heuristique pour le problème du sac à dos multiple MKP. L'approche proposée est comparée à l'heuristique MTHM et au solveur CPLEX. Dans un deuxième temps nous présentons la mise en oeuvre parallèle d'une méthode exacte de résolution de problèmes d'optimisation combinatoire de type sac à dos sur architecture GPU. La mise en oeuvre CPU-GPU de la méthode de Branch and Bound pour la résolution de problèmes de sac à dos a montré une accélération de 51 sur une carte graphique Nvidia Tesla C2050. Nous présentons aussi une mise en oeuvre CPU-GPU de la méthode du Simplexe pour la résolution de problèmes de programmation linéaire. Cette dernière offre une accélération de 12.7 sur une carte graphique Nvidia Tesla C2050. Enfin, nous proposons une mise en oeuvre multi-GPU de l'algorithme du Simplexe, mettant à contribution plusieurs cartes graphiques présentes dans une même machine (2 cartes Nvidia Tesla C2050 dans notre cas). Outre l'accélération obtenue par rapport à la mise en oeuvre séquentielle de la méthode du Simplexe, une efficacité de 96.5 % est obtenue, en passant d'une carte à deux cartes graphiques.

Sous la direction du :
Directeur de thèse
El Baz, Didier
Elkihel, Moussa
Ecole doctorale:Systèmes
laboratoire/Unité de recherche :Laboratoire d'Analyse et d'Architecture des Systèmes (LAAS) - CNRS
Mots-clés libres :Optimisation combinatoire - Sac à dos - Calcul parallèle et distribué - Logistique - Calcul sur GPU - Calcul hybride
Sujets :Electricite, électronique, automatique
Déposé le :01 Jul 2013 16:58