The SOP is a version of the Asymmetric Traveling Salesman Problem (TSP) where precedence constraints on the vertices must be observed. This problem has numerous real life applications in manufacturing and scheduling. In fact some of the unsolved data sets are real life instances of actual manufacturing problems. (http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/)

While TSPs of gigantic size have been solved optimally, optimal solutions to even relatively small order (40+ vertex) SOPs are not yet discovered. The state of the art branch&cut solver from Ascheuer et al. can solve SOPs with a few constraints optimally and can also obtain upper and lower bounds in case if the optimal solution is not reached within the running time limit.

Our algorithm derives lower bounds automatically from an abstraction of the SOP state space. These lower bounds stored in a large database are used in a novel bi-directional branch&bound algorithm. We have already found actual solutions within the upper bounds given by Ascheuer's implementation and these were found much faster for the SOPs with the more constraints. Given unlimited time, we would find the optimal solution. Our algorithm is a general automatic technique and could easily incorporate other types of constraints and even solve other types of problems (such as the Rubik's Cube!).