Resolution Exacte D Un Probleme D Optimisation Combinatoire Np Difficile Sur Grilles De Calcul
Download Resolution Exacte D Un Probleme D Optimisation Combinatoire Np Difficile Sur Grilles De Calcul PDF/ePub or read online books in Mobi eBooks. Click Download or Read Online button to get Resolution Exacte D Un Probleme D Optimisation Combinatoire Np Difficile Sur Grilles De Calcul book now. This website allows unlimited access to, at the time of writing, more than 1.5 million titles, including hundreds of thousands of titles in various foreign languages.
Résolution exacte d'un problème d'optimisation combinatoire NP-difficile sur grilles de calcul
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
Méthodes D'Optimisation Combinatoire Sur Grilles de Calcul
La résolution exacte de problèmes d'optimisation combinatoire de grande taille constitue un vrai défi pour les grilles informatiques. En effet, il est nécessaire de repenser les algorithmes de résolution pour prendre en compte les caracteristiques de tels environnements, notamment leur grande échelle, l'hétérogénéité et la disponibilité dynamique de leurs ressources, et leur nature multi-domaine d'administration. Dans cette thèse, nous avons proposé une nouvelle approche de passage sur grilles de calcul des méthodes exactes de type Branch-and-Bound appelée B&B@Grid. Cette approche est basée sur un codage des unités de travail (sous-problèmes) sous forme d'intervalles permettant de minimiser le coût des communications induites par les opérations de régulationde charge, de tolérance aux pannes et de détection de la terminaison. Cette approche, environ 100 fois plus performante en termes de coût de communication que la meilleure approche connue, a permis la résolution optimale sur la grillenationale Grid5000 d'une instance standard du problème du Flow-Shop restée non résolue depuis une quinzaine d'années.
Une approche efficace pour le passage sur grilles de calcul de méthodes d'optimisation combinatoire
La résolution exacte de problèmes d'optimisation combinatoire de grande taille constitue un défi pour les grilles. En effet, il est nécessaire de repenser les algorithmes de résolution pour prendre en compte les caractéristiques de tels environnements. notamment leur grande échelle. l'hétérogénéité et la disponibilité dynamique de leurs ressources. et leur nature multi-domaine d'administration. Dans cette thèse, nous avons proposé une nouvelle approche de passage sur grilles des méthodes exactes de type Branch-and-Bound appelée B&B@Grid. Cette approche est basée sur un codage des unités de travail sous forme d'intervalles permettant de minimiser le coût des communications induites par les opérations de régulation de charge, de tolérance aux pannes et de détection de la terminaison. Cette approche. environ 100 fois plus performante en terme de coût de communication que la meilleure approche connue. a permis la résolution optimale sur la grille nationale Grid5000 d'une instance standard du problème du Flow-Shop restée non résolue depuis une quinzaine d'années. Pour accélérer la résolution. nous avons également étudié la coopération sur la grille de la méthode exacte avec une méta-heuristique parallèle hybride. Deux modes de coopération ont été considérés : le mode relais où la méta-heuristique est exécutée avant la méthode exacte, le mode co-évolutionnaire où les deux méthodes sont exécutées en parallèle. La mise en oeuvre d'une telle coopération sur la grille nous a amené il proposer une extension du modèle de coopération Linda.