In this paper we introduce an extension of the Traveling Salesman Problem (TSP), which is motivated by an important application in bioinformatics. In contrast to the 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). Besides its application in bioinformatics, the QTSP is a generalization of the Angular-Metric TSP and the TSP with reload costs. Apart from the TSP with quadratic cost structure we also consider the related Cycle Cover Problem with quadratic objective function (QCCP). In this work we present three exact solution approaches and several heuristics for the QTSP. The first exact approach is based on a polynomial transformation to a 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. 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 nodes could be solved to optimality in about ten minutes.

The quadratic traveling salesman problem asks for a tour of minimal total costs where the costs are associated with each of two arcs that are traversed in succession. This structure arises, e.g., if the succession of two arcs represents loading processes in transport networks or a switch between different technologies in communication networks. Based on an integer program with quadratic objective function we present a linearized integer programming formulation and study the corresponding polyhedral structure of the asymmetric quadratic traveling salesman problem (AQTSP), where the costs may depend on the direction of traversal. The constructive approach that is used to establish the dimension of the underlying polytope allows us to prove the facetness of several classes of valid inequalities. Some of them are related to the Boolean quadric polytope. Two new classes are developed that exclude conflicting configurations. Among these the first one is separable in polynomial time, and the separation problem for the second class is \textbfNP-complete. We present a general strengthening approach that allows us to lift valid inequalities for the asymmetric traveling salesman problem to stronger valid inequalities for AQTSP. Applying this approach to the subtour elimination constraints gives rise to facet defining inequalities, but finding a maximally violated inequality among these is \textbfNP-complete. In general, the strengthening approach is not sufficient to obtain a facet. First computational results are presented to illustrate the importance of the new inequalities, especially for the solution of some real-world instances from biology.