In this paper we present an asynchronous branch and bound algorithm for execution on an MIMD system, state sufficient conditions to prevent the parallelism from degrading the performance of this algorithm, and investigate the consequences of having the algorithm executed by nonhomogeneous processing elements. We introduce the notions of perfect parallel time and achieved efficiency to empirically measure the effects of parallelism, because the traditional notions of speedup and processor utilization are not adequate for fully characterizing the actual execution of an asynchronous parallel branch and bound algorithm. Finally we present some computational results obtained for the symmetric traveling salesman problem.

MIMD, asynchronicity, branch and bound, loosely coupled system, nondeterminism, parallel computer, traveling salesman problem
Erasmus School of Economics

Trienekens, H.W.J.M. (1989). Computational experiments with an asynchronous parallel branch and bound algorithm. Retrieved from