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

Bernard Mans*, Catherine Roucairol

*Corresponding author for this work

Research output: Contribution to journalArticle

12 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)57-74
Number of pages18
JournalDiscrete Applied Mathematics
Volume66
Issue number1
DOIs
Publication statusPublished - 22 Apr 1996
Externally publishedYes

Keywords

  • Anomalies
  • Branch and bound algorithm
  • Consistency
  • Parallel processing
  • Scalability
  • Speed-up

Fingerprint Dive into the research topics of 'Performances of parallel branch and bound algorithms with best-first search'. Together they form a unique fingerprint.

Cite this