Abstract EN:

Ces dernières années, de nombreuses avancées dans la résolution exacte de problèmes d'optimisation difficiles ont été enregistrées. Le premier facteur de ces succès est le développement de nouvelles techniques de calcul de bornes inférieures pour ces problèmes et le deuxième facteur est sans aucun doute la progression de la puissance de calcul des machines parallèles en utilisant des grilles de calcul. Le QAP est l'un des problèmes d'Optimisation Combinatoire les plus difficiles. Bien qu'il soit ancien, ce problème suscite encore aujourd'hui beaucoup d'intérêt. A cela, deux raison principales: d'une part, beaucoup de problèmes du monde industriel sont modélisés par cette application; d'autre part, de nombreux autres problèmes d'Optimisation Combinatoire, comme le problème du voyageur de commerce (TSP), ou encore des problèmes de la théorie de graphe tel le problème de clique maximal et problème de partitionnement de graphe s'expriment comme des cas particuliers du QAP. Le travail présenté dans ce mémoire porte sur l'étude de la parallélisation de la méthode Branch-and-Bound. Le modèle de parallélisation est implémenté dans la librairie d'aide à la programmation Bob++ et un algorithme Branch-and-Bound parallèle est proposée pour le QAP. L'algorithme, basé sur une nouvelle technique de cacul de borne inférieur, est développé pour s'exécuter, avec un minimum de changements, sur une large gamme de machines séquentielles et/ou parallèles y compris les larges systèmes distribués comme les grilles de calcul. Les résultats obtenus montrent l'efficacité et extensibilité de l'algorithme