Seminar


       Department of Systems Engineering and Engineering Management,

                    The Chinese University of Hong Kong

------------------------------------------------------------------------------

Title:
A new perspective into solving
the Traveling Salesman Problem by dynamic programming

Speaker:
Dr. Joaquim A. S. Gromicho
Vrije Universiteit, Amsterdam,
The Netherlands & ORTEC International,
Gouda, The Netherlands


Date : November 16, 2005 (Wednesday)

Time : 5:30 p.m. - 6:30 p.m.

Venue : Room 513, William M.W. Mong Engineering Building

(Engineering Building Complex Phase 2), CUHK

Abstract:
Dynamic programming plays an important role in optimization, and particularly
in combinatorial optimization.

The Traveling Salesman Proble (TSP) is one of the most celebrated of the
NP-hard combinatorial problems, and therefore its lowest complexity is still
unknown. However, dynamic programming offers since the work of Held and Karp
in 1962 the lowest known complexity to the problem. Consequently, Dynamic
Programming has a strong theoretical relevance for the TSP.

The practical relevance of Dynamic Programming when applied to the TSP, or
other NP-hard problems, is perceived as being much smaller.

This talk brings Dynamic Programming into a new perspective. From this
perspective we aim at reviving the approach as a practical and competitive
setting to solve realistic TSP instances in both heuristic and optimal senses.

This is joint work with Aukje van den Hoeven, VU & ORTEC.

Bio:
Joaquim A. S. Gromicho is a Senior Software Architect at ORTEC Software
Development within ORTEC International and an Assistant Professor at the
Econometrics Department of the Vrije Universiteit in Amsterdam. He received
his Ph.D. from the Erasmus Universiteit Rotterdam and his MSc from the
Universidade de Lisboa. His research interests are on optimization, with a
special emphasis towards Combinatorial Optimization and its applications to
Logistics.