Public lecture series and training in the complementary skill of self-promotion

Public lecture series

THE TRAVELING SALESMAN PROBLEM

July 30, 14--15:30 and 15:45--17.15

featured by Vašek Chvátal (Concordia University Montreal and Charles University, Prague)

in the lecture room S5 of the Schol of Informatics, Charles University, 

Malostranske nam. 25, Prague 1, Czech Republic

The first part (14:00–15:30) of this lecture will be aimed at general public:

I will trace the history of the traveling salesman problem (TSP) and remi-

nisce about the development of Concorde, the TSP solver written by David

Applegate, Bob Bixby, Bill Cook, and myself.  (This part will train students

in the complementary skill of self-promotion.)

In the second part (15:45–17.15), I will discuss some of the innovations in-

troduced in Concorde that were instrumental in solving difficult instances of

the TSP:

•

getting subtour cuts from parametric connectivity,

•

getting subtour cuts from tour intervals,

•

getting comb cuts from the consecutive ones property,

•

strong branching.