How to cope with anomalies in parallel approximate branch-and-bound algorithms
Guojie Li, Benjamin Wan-Sang Wah · 1984
Abstract: A genera! technique for solving a wide variety of search problems is the branch-and-bound (B&B) algorithm. We have adapted and extended B&B algorithms for parallel processing. Anomalies owing to parallelism may occur.-In this paper sufficient conditions to guarantee that parallelism will not degrade the performance are presented. Necessary condi-tions for allowi & parallelism to have a speedup greater than the number of processors are also shown. Anomalies are found to occur infrequently when optima! solutions are sought; how-ever, they are frequent in- approximate B&B algorithms. Theoretical analysis and simulations show that a best-first search is robust for parallel processing. 1.