Guo-jie Li, Benjamin W. Wah
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 conditions for allowing parallelism to have a speedup greater than the number of processors are also shown. Anomalies are found to occur infrequently when optimal solutions are sought; however, they are frequent in approximate B&B algorithms. Theoretical analysis and simulations show that a best-first search is robust for parallel processing.