A parallel best-first B&B algorithm and its axiomatization

A new parallel best-first branch and bound algorithm designed for distributed memory machines is presented. Starting from an axiomatization of the branch and bound paradigm, the authors develop the notion of fringes in the branch and bound tree which correspond to sets of equivalent problems. The algorithm proposed evaluates these sets of problems in parallel, during each phase of its execution. These computationally intensive phases alternate with control phases where synchronization and information exchange between processors take place. The authors use a probabilistic model for predicting the performance of this algorithm. The performance obtained on multiple instruction/multiple data (MIMD)-DM multiprocessors for the asymmetric non-Euclidean traveling salesman problem is discussed