Exact algorithms and heuristics for the Quadratic Traveling Salesman Problem with an application in bioinformatics ?
In this paper we introduce an extension of the Traveling Salesman Problem (TSP TSP ), which is motivated by an important application in bioinformatics. In contrast to the TSP TSP the costs do not only depend on each pair of two nodes traversed in succession in a cycle but on each triple of nodes traversed in succession. This problem can be formulated as optimizing a quadratic objective function over the traveling salesman polytope, so we call the combinatorial optimization problem quadratic TSP  (QTSP QTSP ). Besides its application in bioinformatics, the QTSP QTSP is a generalization of the Angular-Metric TSP TSP and the TSP TSP with reload costs. Apart from the TSP TSP with quadratic cost structure we also consider the related Cycle Cover Problem with quadratic objective function (QCCP QCCP ). In this work we present three exact solution approaches and several heuristics for the QTSP QTSP . The first exact approach is based on a polynomial transformation to a TSP TSP , which is then solved by standard software. The second one is a branch-and-bound algorithm that relies on combinatorial bounds. The best exact algorithm is a branch-and-cut approach based on an integer programming formulation with problem-specific cutting planes. All heuristical approaches are extensions of classic heuristics for the TSP TSP . Finally, we compare all algorithms on real-world instances from bioinformatics and on randomly generated instances. In these tests, the branch-and-cut approach turned out to be superior for solving the real-world instances from bioinformatics. Instances with up to 100 100 nodes could be solved to optimality in about ten minutes.
traveling salesman problem bioinformatics branch-and-bound branch-and-cut heuristical methods exact methods