Linear Models and Computational Experiments for the Quadratic TSP

We consider the Symmetric Quadratic Traveling Salesman Problem (SQTSP), which is a generalization of the classical TSP where each sequence of two consecutive edges in the tour gives rise to a certain cost value. For the standard linearization we apply a purely integral subtour elimination strategy which outperforms the usual fractional separation routine in computational experiments, even if strengthened inequalities are added. The maximization version of the problem is introduced and turns out to benefit from this strengthening. Finally, a new geometry-based linearization with only a linear number of additional variables is presented for the Angular Metric TSP and variants thereof. It is faster than the other approaches for medium-sized instances of one of the variants.