Coping with Anomalies in Parallel Branch-and-Bound Algorithms
Coping with Anomalies in Parallel Branch-and-Bound Algorithms
复制标题
处理并行分支定界算法中的异常
DOI：
10.1109/tc.1986.5009434
复制
发表时间：
1986
影响因子：
3.7
通讯作者：
B. Wah
中科院分区：
文献类型：
--
作者：
Guo;B. Wah
一种可用于解决各种离散优化问题的通用技术是分支定界算法。我们对分支定界算法进行了改进和扩展，使其适用于并行处理。这些算法的计算效率取决于允许函数、数据结构和搜索策略。可能会出现由于并行性而导致的异常。在这一对应关系中，研究了并行分支定界算法使用与相应的串行算法相同的搜索策略的异常。给出了保证性能不因并行性而降低的充分条件，以及允许并行性的加速比大于处理器数目的必要条件。
A general technique that can be used to solve a wide variety of discrete optimization problems is the branch-and-bound algorithm. We have adapted and extended branch-and-bound algorithms for parallel processing. The computational efficiency of these algorithms depends on the allowance function, the data structure, and the search strategies. Anomalies owing to parallelism may occur. In this correspondence, anomalies of parallel branch-and-bound algorithms using the same search strategy as the corresponding serial algorithms are studied. Sufficient conditions to guarantee no degradation in performance due to parallelism and necessary conditions for allowing parallelism to have a speedup greater than the number of processors are presented.