Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00077107
Contributor : Rapport de Recherche Inria <>
Submitted on : Monday, May 29, 2006 - 2:49:08 PM
Last modification on : Thursday, February 11, 2021 - 2:50:07 PM
Long-term archiving on: : Friday, May 13, 2011 - 10:42:48 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

294

Files downloads

155