Performances of parallel branch and bound algorithms with best-first search

作     者：Mans, B Roucairol, C 

作者机构：UNIV VERSAILLESF-78000 VERSAILLESFRANCE 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：1996年第66卷第1期

页      面：57-74页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：anomalies branch and bound algorithm consistency parallel processing scalability speed-up 

摘      要：This paper analyzes the performances of parallel branch and bound algorithm with best-first search strategy by examining various anomalies on the expected speed up: detrimental, acceleration and detrimental acceleration. Since the best evaluation is not always sufficient to distinguish the best node to choose with best-first search strategy, we define tie breaking rules for cases when nodes have the same value: the fifo, the lifo and the consistent rules. The purpose of the paper is to convey, through bounds of the parallel execution for each tie breaking rule, an understanding of the nature of the anomalies, the range of their impact and a comparison of their efficiency to cope with these anomalies. Sufficient and necessary conditions are given regarding the predisposition for each of the three classes of anomalous behavior. For comparison, we introduce a propriety of proneness to anomaly. In particular, we show that the consistent rule on best-first search Branch and Bound algorithm may be the weaker solution to cope the detrimental acceleration anomaly. Finally, we prove that the fifo rule is theoretically and practically efficient.