A parallel branch-and-bound algorithm with history-based domination
A parallel branch-and-bound algorithm with history-based domination
复制标题
一种基于历史支配的并行分支定界算法
DOI：
10.1145/3503221.3508415
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Muyan-Özçelik, Pinar
中科院分区：
文献类型：
--
作者：
Gonggiatgul, Taspon;Shobaki, Ghassan;Muyan-Özçelik, Pinar
本文描述了一种基于历史支配技术的并行分枝定界(B&B)算法，并将其应用于序列排序问题(SOP)。据我们所知，该算法是第一个包含基于历史支配技术的并行B&B算法，也是第一个使用纯B&B方法求解SOP的并行B&B算法。该算法采用了基于池的方法，并使用了一系列我们开发的新技术来实现对解空间的有效并行探索，包括并行历史控制、历史表内存管理和线程重启技术。使用SOPLIB和TSPLIB基准测试对所提出的算法进行了实验评估。结果表明，在中等难度的情况下，使用10个线程，时间限制为1小时，该算法在SOPLIB上的几何平均加速比为19.9，在TSPLIB上的几何平均加速比为10.23，在17个实例上的超线性加速比高达65倍。
In this paper, we describe a parallel Branch-and-Bound (B&B) algorithm with a history-based domination technique, and we apply it to the Sequential Ordering Problem (SOP). To the best of our knowledge, the proposed algorithm is the first parallel B&B algorithm that includes a history-based domination technique and is the first parallel B&B algorithm for solving the SOP using a pure B&B approach. The proposed algorithm takes a pool-based approach and employs a collection of novel techniques that we have developed to achieve effective parallel exploration of the solution space, including parallel history domination, history table memory management, and a thread restart technique. The proposed algorithm was experimentally evaluated using the SOPLIB and TSPLIB benchmarks. The results show that using ten threads with a time limit of one hour on the medium-difficulty instances, the proposed algorithm gives a geometric-mean speedup of 19.9 on SOPLIB and 10.23 on TSPLIB, with super-linear speedups up to 65x seen on 17 instances.
DOI：
--
发表时间：
2017
期刊：
IEEE Symposium Series on Computational Intelligence
影响因子：
--
作者：
J. Jamal;Ghassan Shobaki;V. Papapanagiotou;L. Gambardella;R. Montemanni
通讯作者：
R. Montemanni