Spring 2015 Seminar Series

DATE: 4/30/15
LOCATION: E51-395
TIME: 4:15pm
Reception immediately following

SPEAKER:
Bill Cook

TITLE
Edge Elimination in the Traveling Salesman Problem

ABSTRACT
Given a collection of cities, together with the cost of travel between each pair of them, the traveling salesman problem (TSP) is to find the cheapest tour that visits them all and returns to your starting point. The computational study of the TSP goes back to a 1954 paper by Dantzig, Fulkerson, and Johnson, where the authors introduce the well-known cutting-plane method for discrete optimization. The second half of their paper presents another idea, namely, utilizing local information to determine that certain pairs of cities cannot be visited consecutively in any optimal tour. We explore the use of this idea to reduce the variable set for large-scale instances of the TSP.

 

This talk is based on joint work with Keld Helsgaun, Stefan Hougardy, and Rasmus Schroeder.