Anomalies in parallel branch-and-bound algorithms

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.

REFERENCES

• 1: Agin, N. Optimum seeking with branch-and-bound. Manage. Sci. 13, pp. B176-B185.
• 2: Desai, B. The BPU, a staged parallel processing system to solve the zero-one problem. Proc. ICS '78, 1978, pp. 802-817.
• 3: Desai, B. A parallel microprocessing system. Proc. 1979 Int. Conf. Parallel Processing, 1979.
• 4: Desai, B. A parallel processing system to solve the 0-1 programming problem. Ph.D. dissertation, McGill University, Jan. 1977.
• 5: E1-Dessouki, O. and Huen, W. Distributed enumeration on network computers IEEE Trans. Computers C-29, 1980, pp. 818-825.
• 6: Fox, B., Lenstra, J., Rinnooy Kan, A. and Schrage, L. Branching from the largest upper bound: Folklore and fact. Europ. J. Op. Res. 2, 1978, pp. 191-194.
• 7: Graham, R. Bounds on multiprocessor timing anomalies. SIAM J. Applied Math. 17, 2, 1969, pp. 416-429.
• 8: J. Archer Harris , David R. Smith, Hierarchical multiprocessor organizations, Proceedings of the 4th annual symposium on Computer architecture, p.41-48, March 23-25, 1977
• 9: Held, M. and Karp, R. The traveling salesman problem and minimum spanning trees: Part II, Math. Prog. 1, 1971, pp. 6-25.
• 10: Horowitz. E. and Sahni. S. Fundamentals of Computer Algorithms. Computer Science Press, Inc., Bethesda, MD. 1978.
• 11: Ignall, E. and Schrage, L. Application of the branch-and-bound technique to some flow-shop scheduling problems. Oper. Res. 13, 1965, pp. 400-412.
• 12: Kohler, W. and Steiglitz, K. Enumerative and iterative computational approaches. In E. Coffman (ed.) Computer and Job-Shop Scheduling Theory, John Wiley and Sons, Inc., New York, 1976, pp. 229- 287.
• 13: Lawler, E. and Wood, D. Branch-and-bound methods: A survey. Oper. Res. 14, 1966, pp. 699-719.
• 14: Mitten, L. Branch-and-bound methods: General formulation and properties. Oper. Res. 18, 1970, pp. 24-34.
• 15: Nils J. Nilsson, Problem-Solving Methods in Artificial Intelligence, McGraw-Hill Pub. Co., 1971
• 16: Benjamin W. Wah , Y. W. Ma, MANIP-a parallel computer system for implementing branch and bound algorithms, Proceedings of the 8th annual symposium on Computer Architecture, p.239-262, May 12-14, 1981, Minneapolis, Minnesota, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
anomalous behavior, branch-and-bound, parallel algorithms