Performances des algorithmes branch-and-bound paralleles a strategie meilleur d'abord

Bernard Mans 1 Catherine Roucairol 1
1 ParaDis
INRIA Rocquencourt
Résumé : Les algorithmes Branch and Bound "meilleur d'abord" sont utilisees generalement pour resoudre les problemes d'Optimisation Combinatoire NP-difficiles. Lors de leur parallelisation, trois differents types d'anomalies sur l'acceleration (speed-up) attendue peuvent survenir : desastreuse, d'acceleration ou de prejudice d'acceleration. Un nouveau modele de Branch and Bound parallele, permettant d'analyser les performances paralleles esperees, est introduit. La strategie de recherche fondee sur la meilleure evaluation etant insuffisante pour distinguer les sommets de meme evaluation lors de la selection du nouveau candidat a la separarion, nous decrivons trois directives de selection concernant les sommets d'evaluation identiques: la regle fifo, la regle lifo et la regle consistante. Nous calculons pour chacune d'entre elles des bornes tres fines, souvent atteignables, rendant compte des temps d'executions paralleles potentiels. Nous donnons des conditions necessaires et suffisantes d'apparition de chacune des anomalies. L'ensemble de ces resultats permet d'introduire une propriete de predisposition aux anomalies, dont nous deduisons des criteres de choix precis pour les strategies enoncees. Differentes relaxations des hypotheses du modele sont discutees et comparees quant a la qualite des reelles implementations et des outils d'analyse necessaires.
Type de document :
Rapport
[Rapport de recherche] RR-1716, INRIA. 1992
Liste complète des métadonnées

https://hal.inria.fr/inria-00077107
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 29 mai 2006 - 14:49:08
Dernière modification le : vendredi 16 septembre 2016 - 15:11:11
Document(s) archivé(s) le : vendredi 13 mai 2011 - 22:42:48

Fichiers

Identifiants

  • HAL Id : inria-00077107, version 1

Collections

Citation

Bernard Mans, Catherine Roucairol. Performances des algorithmes branch-and-bound paralleles a strategie meilleur d'abord. [Rapport de recherche] RR-1716, INRIA. 1992. 〈inria-00077107〉

Partager

Métriques

Consultations de la notice

233

Téléchargements de fichiers

108