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

Overview & Synopsis

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.