How to Cope With Anomalies in Parallel Approximate Branch-and-Bound

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 4

Automated Reasoning

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.