Spring 2005 Seminar Series

DATE: Thursday, May 5, 2005
LOCATION: E40-298
TIME: 4:15pm
Reception immediately following in the Philip M. Morse Reading Room, E40-106

SPEAKER:
Gilbert Laporte
Professor of Operations Research
Department of Management Sciences
HEC Montréal

TITLE
Branch-and-Cut Algorithms for the m-Peripatetic Salesman Problem

ABSTRACT
In the m-Peripatetic Traveling Salesman Problem (m-PSP) the aim is to determine m edge-disjoint Hamiltonian cycles of minimum total cost on a graph. I will describe exact branch-and-bound procedures for the m-PSP, together with some families of valid inequalities. Computational results will be reported on random and Euclidean graphs. This work was done jointly with Eric Duchenne and Frederic Semet, Universite de Valenciennes, France.