Abstract :

The asymmetric traveling salesman problem is defined on a directed graph G=(V,A), where V is the set of vertices and A is the set of edges with a cost, cij defined on A. The TSP problem is to determine an optimal tour( Hamiltonian circuit) over G. As is the case with most combinatorial optimization problems, exact algorithms for solving the TSP combine polyhedral results with enumeration, where the efficiency of enumeration depends on the strength of the LP relaxation of the given formulation. In this talk, we introduce the Traveling Salesman Problem(TSP) and present a review and classification of the formulations of the TSP. In particular, we discuss the LP relaxations of the formulations and do a comparative analysis of the same.