The Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is arguably the most famous problem in combinatorial optimization. The speaker has made a number of contributions to the study of this problem, including the identification of comb inequalities in 1973 and, more recently, the development of the Concorde algorithm, with Applegate, Bixby and Cook. This algorithm is capable of solving large scale instances to optimality. Important milestones and results in the study of the TSP will be reported.