A PARALLEL BEST-FIRST B&B ALGORITHM AND ITS AXIOMATIZATION
作者:
M. GENGLER,
G. CORAY,
期刊:
Parallel Algorithms and Applications
(Taylor Available online 1994)
卷期:
Volume 2,
issue 1-2
页码: 61-80
ISSN:1063-7192
年代: 1994
DOI:10.1080/10637199408915407
出版商: Taylor & Francis Group
关键词: Combinatorial optimization;branch and bound;axiomatization;parallelization;distributed memory;synchronization;probabilistic model;D.1.3;D.4.1;D.4.2;F.1.2;F.2.2;G.2.1;I.6.4
数据来源: Taylor
摘要:
We present a new parallel best-first Branch and Bound algorithm designed for distributed memory machines. Starting from an axiomatization of the Branch and Bound pardigm, we develop the notion of fringes in the Branch and Bound tree which correspond to sets of equivalent problems. The algorithm proposed in this paper evaluates these sets of problems in parallel, during each phase of its execution. These computationally intensive phases alternate with control phases where synchronization and information exchange between processors lakes place. We use a probabilistic model for predicting the performances of this algorithm. Finally, we discuss the performances obtained on MIMD-DM multiprocessors for the asymmetric non-Euclidean Traveling Salesman Problem.
点击下载:
PDF (318KB)
返 回