Performances des algorithmes branch-and-bound paralleles a strategie meilleur d'abord - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1992

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

Bernard Mans
  • Fonction : Auteur
Catherine Roucairol
  • Fonction : Auteur

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-1716.pdf (1.68 Mo) Télécharger le fichier

Dates et versions

inria-00077107 , version 1 (29-05-2006)

Identifiants

  • HAL Id : inria-00077107 , version 1

Citer

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⟩
191 Consultations
87 Téléchargements

Partager

Gmail Facebook X LinkedIn More