The asymmetric travelling salesman problem: Lower bounds and a new separation algorithm

Several integer programming formulations to the Asymmetric Travelling Salesman Problem have been proposed in the literature. We analyze the lower bounds produced by the linear relaxation of two integer programming formulations that model the Asymmetric Travelling Salesman Problem like a flow problem in a directed graph. We implemented a cutting plane algorithm that uses some separation routines from the literature for classes of symmetric constraints. A new separation algorithm for a class of asymmetric constraints was also proposed and used in the study. Preliminary computational tests were conducted on randomly generated instances and on some real world instances from the literature. The lower bounds obtained were close to optimality and the proposed separation algorithm has been shown to be very effective.