Parallel branch and bound on an MIMD system

Abstract

In this paper we give a classification of parallel branch and bound algorithms and\ndevelop a class of asynchronous branch and bound algorithms for execution on an MIMD system.\nWe develop sufficient conditions to prevent the anomalies that can occur due to the\nparallelism, the asynchronicity or the nondeter- minism, from degrading the performance of\nthe algorithm. Such conditions were known already for the synchronous case. It turns out that these conditions are sufficient for asynchronous algorithms as well. We also investigate the consequences of nonhomogeneous processing elements in a parallel computer system.\nWe introduce the notions of perfect parallel time and achieved efficiency to empirically\nmeasure the effects of parallelism, because the traditional notions of speedup and efficiency are not capable of fully characterizing the actual execution of an asyn-chronous parallel algorithm.\nFinally we present some computational results obtained for the symmetric traveling\nsalesman problem.