The quadratic traveling salesman problem asks for a tour of minimal costs where the costs are associated with each two arcs that are traversed in succession. This structure arises, e. g., if the succession of two arcs represents the costs of loading processes in transport networks or a switch between different technologies in communication networks. Based on a quadratic integer program 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 polyhedron allows to prove the facetness of several classes of valid inequalities. Some of them are related to the Boolean quadric polytope. Two new classes are presented that exclude conflicting configurations. Among these the first one is separable in polynomial time, the separation problem for the second class is NP-complete under certain conditions. We provide a general strengthening approach that allows to lift valid inequalities for the asymmetric traveling salesman problem (ATSP) 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 NP-complete. For the (D_3)-, (D_4^-)-, (D_4^+)-inequalities of the ATSP the strengthening approach is not sufficient to obtain a facet. First computational results are presented to illustrate the importance of the new inequalities. In particular, with these inequalities the running times can be improved for some real-world instances from biology by orders of magnitude in comparison to other state of the art methods in the literature.
Citation
Preprint 2011-19, Fakultaet für Mathematik, Technische Universitaet Chemnitz, D-09107 Chemnitz, December 2011