Department of Mathematics

Indian Institute Of Technology Madras , Chennai
  • Mathematics Department Shifted to NAC Office of the Department of Mathematics is moved from HSB to New Academic Complex (NAC) 5th and 6th Floor

Formulations of the Traveling Salesman Problem and Linear Programming Relaxations

Speaker : Dr. Usha Mohan, Department of Management Studies, IIT Madras.

05-10-2017

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.

Key Speaker Dr. Usha Mohan, Department of Management Studies, IIT Madras.
Place NAC 522
Start Time 3:00 PM
Finish Time 4:00 PM
External Link None