Analysis and implementation of branch-and-bound algorithms on a hypercube multicomputer

The feasibility of implementing best-first (best-bound) branch-and-bound algorithms on hypercube multicomputers is discussed. The computationally-intensive nature of these algorithms might lead a causal observer to believe that their parallelization is trivial. However, as the number of processors grows, two goals must be satisfied to some degree in order to maintain a reasonable level of efficiency. First, processors must be kept busy doing productive work (i.e. exploring worthwhile subproblems). Second, the number of interprocessor communications must be minimized along the critical path in the state-space tree from the original problem to the subproblem yielding a solution. It is difficult to improve performance in one of these areas without degrading performance in the other. Analytical models for the execution time of loosely synchronous and asynchronous parallel branch-and-bound algorithms are presented, and the models are validated with data from the execution of five algorithms that solve the traveling salesperson problem