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

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.