Article ID: | iaor19921125 |
Country: | Switzerland |
Volume: | 33 |
Start Page Number: | 331 |
End Page Number: | 349 |
Publication Date: | Dec 1991 |
Journal: | Annals of Operations Research |
Authors: | Clausen Jens, Larsson-Traff Jesper |
Keywords: | heuristics, computational analysis: parallel computers |
Parallel processing is one of the essential concepts in the attempts to increase the computational power available for solving continuous and discrete optimization problems. In the case where an optimization algorithm is search-based, crucial issues of parallel distributed implementations are work-load distribution and granularity, i.e. how to distribute the search space among processors and how to control the amount of processing between interprocessor communication. The present paper compares distributed implementations of two branch-and-bound algorithms for the graph partitioning problem: Given an undirected graph with an even number of edges and weights assigned to each edge, partition the vertices into two subsets of equal size such that the sum of the costs of edges connecting vertices in different subsets is as small as possible. The problem is known to be NP-complete. The two branch-and-bound methods compared differ in design strategy: One is based on time-consuming bound calculations leading to tight bounds and thus a narrow search tree with few nodes, whereas the other employs an easy bound calculation scheme leading to a larger search tree. Both have been implemented on an iPSC-hypercube with 32 processors. The authors investigate the influence of the design strategy on the performance of the algorithms.