La résolution jusqu'à l'optimalité de problèmes d'optimisation combinatoire NP-difficiles nécessite une mise en oeuvre de méthodes de plus en plus complexes qui consomment de plus en plus de puissance de calcul. L'objectif de notre travail est de paralléliser un algorithme de "Branch and Cut" pour résoudre jusqu'à l'optimalité des instances difficiles du voyageur de commerce. Dans la première partie de notre travail, nous présentons les composantes principales de l'algorithme du "Branch and Cut". Nous étudions ensuite le problème du voyageur de commerce par une approche polyédrale. Nous donnons enfin une description détaillée de notre implémentation de l'algorithme du "Branch and Cut". Dans la deuxième partie, Nous commençons par une brève présentation du parallélisme, et un état de l'art des études menées sur la parallélisation de l'algorithme du "Branch and Bound". Puis, nous proposons plusieurs modèles de parallélisations de l'algorithme du "Branch and Cut". Nous décrivons ensuite la stratégie de contrôle de la recherche arborescente qu'on a adopté, les mécanismes de minimisation des coûts liés aux différentes étapes de la communication entre les processeurs et les stratégies d'équilibrages. Nous terminons en donnant les résultats obtenus sur le IBM-SP1.
Publié le : 1998-12-14
Classification:
parallelism,
Branch and Cut and Price,
Symmetric Traveling Salesman Problem,
parallélisme,
"Branch and Cut and Price",
problème du voyageur de commerce,
[INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation,
[MATH]Mathematics [math]
@article{tel-00004801,
author = {Bouzgarrou, Mohamed Ekbal},
title = {Parallel Branch and Cut for the Traveling Salesman Problem},
journal = {HAL},
volume = {1998},
number = {0},
year = {1998},
language = {fr},
url = {http://dml.mathdoc.fr/item/tel-00004801}
}
Bouzgarrou, Mohamed Ekbal. Parallel Branch and Cut for the Traveling Salesman Problem. HAL, Tome 1998 (1998) no. 0, . http://gdmltest.u-ga.fr/item/tel-00004801/