A branch and bound algorithm for the sequential ordering problem

The Sequential Ordering Problem (SOP) is the problem of finding the shortest hamiltonian path in a graph while satisfying given precedence constraints regarding the order in which the nodes are visited. This classical optimization problem has many real-world applications, particularly in production planning, scheduling and transportation. We propose a branch and bound-based approach which can be used to solve medium instances (up to 30 nodes) of the problem to optimality in reasonable time. It does not require any specialized software for solving Mixed Integer Linear programs (MILP) and performs well particularly for heavily-constrained instances. The performance of the algorithm is tested on benchmark problems found in the TSPLIB online library.