Anomalies in parallel branch-and-bound algorithms

1 June 1984

journal article
Published by Association for Computing Machinery (ACM) in Communications of the ACM

Vol. 27 (6) , 594-602
https://doi.org/10.1145/358080.358103

Abstract

We consider the effects of parallelizing branch-and-bound algorithms by expanding several live nodes simultaneously. It is shown that it is quite possible for a parallel branch-and-bound algorithm using n2 processors to take more time than one using n1 processors, even though n1 n2. Furthermore, it is also possible to achieve speed-ups that are in excess of the ratio n2/n1. Experimental results with the 0/1-Knapsack and Traveling Salesman problems are also presented.

Keywords

This publication has 9 references indexed in Scilit:

Distributed Enumeration on Between Computers
IEEE Transactions on Computers, 1980
Branching from the largest upper bound Folklore and facts
European Journal of Operational Research, 1978
Hierarchical multiprocessor organizations
Published by Association for Computing Machinery (ACM) ,1977
The traveling-salesman problem and minimum spanning trees: Part II
Mathematical Programming, 1971
Branch-and-Bound Methods: General Formulation and Properties
Operations Research, 1970
Bounds on Multiprocessing Timing Anomalies
SIAM Journal on Applied Mathematics, 1969
Optimum Seeking with Branch and Bound
Management Science, 1966
Branch-and-Bound Methods: A Survey
Operations Research, 1966
Application of the Branch and Bound Technique to Some Flow-Shop Scheduling Problems
Operations Research, 1965