Discussion Papers, Department of Business and Management Science, Norwegian School of Economics (NHH)
A new Lagrangean Approach for the Travelling Salesman Problem
() and Jörg Kalcsics
Abstract: In this paper, we use a reformulation of the symmetric and
the asymmetric travelling salesman problem more suitable for Lagrangean
relaxation and analyse the new approach on examples from TSP Lib.
Furthermore the Lagrangean relaxed subproblems are travelling salesman
alike which means that almost all that is known on the travelling salesman
polytope can be used when the subproblems are to be solved.
Keywords: Travelling Salesman; Lagrangean Relaxation; Mathematical Programming; (follow links to similar papers)
JEL-Codes: C60; (follow links to similar papers)
11 pages, January 19, 2015
Before downloading any of the electronic versions below
you should read our statement on
for viewing Postscript files and the
Acrobat Reader for viewing and printing pdf files.
Full text versions of the paper:
Questions (including download problems) about the papers in this series should be directed to Stein Fossen ()
Report other problems with accessing this service to Sune Karlsson ()
or Helena Lundin ().
Design by Joachim Ekebom