Solving the sequential ordering problem using branch and bound

摘要

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.