A Polyhedral Study of the Quadratic Traveling Salesman Problem

In this paper we summarize some of the results of the author’s Ph.D.-thesis. We consider an extension of the traveling salesman problem (TSP). Instead of each path of two nodes, an arc, the costs depend on each three nodes that are traversed in succession. As such a path of three nodes, a 2-arc, is present in a tour if the two corresponding arcs are contained in that tour, we speak of a quadratic traveling salesman problem (QTSP). This problem is motivated by an application in biology, special cases are the TSP with reload costs as well as the angular-metric TSP. Linearizing the quadratic objective function, we derive a linear integer programming formulation and present a polyhedral study of the associated polytope. This includes the dimension as well as three groups of facet-defining inequalities. Some are related to the Boolean quadric polytope and some forbid conflicting configurations. Furthermore, we describe approaches to strengthen valid inequalities of TSP in order to get stronger inequalities for QTSP.