Solving the Sequential Ordering Problem with Automatically Generated Lower Bounds

The Sequential Ordering Problem (SOP) is a version of the Asymmetric Traveling Salesman Problem (ATSP) where precedence constraints on the vertices must also be observed. The SOP has many real life applications and it has proved to be a great challenge (there are SOPs with 40-50 vertices which have not been solved optimally yet with significant computational effort). We use novel branch&bound search algorithms with lower bounds obtained from homomorphic abstractions of the original state space. Our method is asymptotically optimal. In one instance, it has proved a solution value to be optimal for an open problem while it also has matched best known solutions quickly for many unsolved problems from the TSPLIB. Our method of deriving lower bounds is general and applies to other variants of constrained ATSPs as well.