In this paper we consider the Asymmetric Quadratic Traveling Salesman Problem. Given a directed graph and a function that maps every pair of consecutive arcs to a cost, the problem consists in finding a cycle that visits every vertex exactly once and such that the sum of the costs is minimum. We propose an extended Linear Programming formulation that has a variable for each cycle in the graph. Since the number of cycles is exponential in the graph size, we propose a column generation approach. We compare the bounds resulting from this new formulation with those obtained by some linearization techniques for 0-1 quadratic optimization or specifically proposed for the QTSP. Computational results on some set of benchmarks used in the literature show that the column generation approach is very promising.

## Article

View Lower bounding procedure for the Asymmetric Quadratic Traveling Salesman Problem