Solving the sequential ordering problem using branch and bound
Solving the sequential ordering problem using branch and bound
复制标题
使用分支定界解决顺序排序问题
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
R. Montemanni
中科院分区：
文献类型：
--
作者：
J. Jamal;Ghassan Shobaki;V. Papapanagiotou;L. Gambardella;R. Montemanni
顺序排序问题（SOP）是一个NP硬性问题，在调度，物流和编译器的域中具有广泛的应用程序。强大的计算机的开发和有效的算法技术使得可以设计出可以解决此问题更大实例的精确算法。在本文中，我们使用分支机构（B＆B）方法为此问题提供了一种增强的精确算法。所提出的算法基于一种新的低结合技术和局部搜索统治技术。新的低结合技术使用动态的匈牙利算法来解决SOP的最低成本完美匹配的放松。如果找到更好的部分解决方案，则本地搜索统治技术将在B＆B树中当前节点下方的子树修复。使用三种不同的基准套件通过实验评估所提出的算法的性能：TSPLIB，SOPLIB和编译器。实验评估的结果表明，所提出的算法发现的溶液比以前提出的算法快得多。对于三个相应的基准组，提出的方法将最佳差距显着降低至0.217、0.122和0.004，并关闭了以前打开的五个实例。
The Sequential Ordering Problem (SOP) is an NP-hard problem with a wide range of applications in the domains of scheduling, logistics and compilers. The development of powerful computers and effective algorithmic techniques has made it possible to devise exact algorithms that can solve larger instances of this problem. In this paper, we present an enhanced exact algorithm for this problem using a branch-and-bound (B&B) approach. The proposed algorithm is based on a new lower-bound technique and a local-search domination technique. The new lower-bound technique uses the dynamic Hungarian algorithm to solve a Minimum-Cost Perfect Matching relaxation of the SOP. The local search domination technique prunes the sub-tree below the current node in the B&B tree if a better partial solution is found. The performance of the proposed algorithm is evaluated experimentally using three different benchmark suites: TSPLIB, SOPLIB and COMPILERS. The results of the experimental evaluation show that the proposed algorithm finds exact solutions considerably faster than previously proposed algorithms. The proposed approach significantly reduces the optimality gap to 0.217, 0.122, and 0.004 for the three respective benchmark sets, and closes five instances that were previously open.