Two General Lifting Approaches for the Quadratic Traveling Salesman Problem

Anja Fischer^*, Frank Fischer and Christoph Helmberg

The symmetric quadratic traveling salesman problem (SQTSP) asks for a cost minimal tour in an undirected graph where the costs depend on each three nodes that are traversed in succession. It is an extension of the well-known symmetric traveling salesman problem (STSP) where the costs depend on each two nodes traversed in the tour. The SQTSP can be formulated as an integer optimization problem over the polytope associated with the STSP together with a quadratic cost function. We study the polytope arising from a linearization of the quadratic integer programming formulation. Valid inequalities of STSP remain valid for SQTSP but in most cases they can be improved. We present two general lifting approaches for strengthening inequalities of STSP. The first one can be applied to all inequalities with nonnegative coefficients, the second to arbitrary clique tree inequalities, which are known to be facet defining for STSP. Applying both approaches to the subtour elimination constraints we derive the facet-defining conflicting edges inequalities as well as new facet classes for SQTSP. Furthermore we extend the presented approach to the asymmetric quadratic traveling salesman problem (AQTSP) and derive symmetric and non-symmetric strengthened clique tree inequalities.

Mathematics Subject Classification: 90C57

Keywords: polyhedral combinatorics; lifting approach; traveling salesman problem

Minisymposion: Nonlinear Mixed Integer Programming and Conic Relaxations