A PARALLEL BEST-FIRST B&B ALGORITHM AND ITS AXIOMATIZATION

Abstract

We present a new parallel best-first Branch and Bound algorithm designed for distributed memory machines. Starting from an axiomatization of the Branch and Bound pardigm, we develop the notion of fringes in the Branch and Bound tree which correspond to sets of equivalent problems. The algorithm proposed in this paper 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 lakes place. We use a probabilistic model for predicting the performances of this algorithm. Finally, we discuss the performances obtained on MIMD-DM multiprocessors for the asymmetric non-Euclidean Traveling Salesman Problem.

KEY WORDS:

• Combinatorial optimization
• branch and bound
• axiomatization
• parallelization
• distributed memory
• synchronization
• probabilistic model

C.R. CATEGORIES:

• D.1.3
• D.4.1
• D.4.2
• F.1.2
• F.2.2
• G.2.1
• I.6.4