Scandinavian Working Papers in Business Administration
Discussion Papers,
Norwegian School of Economics, Department of Business and Management Science
No 2015/4: A new Lagrangean Approach for the Travelling Salesman Problem
Kurt Jörnsten () and Jörg Kalcsics ()
Additional contact information
Kurt Jörnsten: Dept. of Business and Management Science, Norwegian School of Economics, Postal: NHH , Department of Business and Management Science, Helleveien 30, N-5045 Bergen, Norway
Jörg Kalcsics: Institute of Operations Research, Karlsruhe Institute of Technology, Postal: Karlsruhe Institute of Technology, Institute of Operations Research, Englerstr. 11, Gebäude 11.40, 2. OG, D-76128 Karlsruhe, Germany
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
JEL-codes: C60
11 pages, January 19, 2015
Full text files
274520
- Norwegian School of Economics, Department of Business and Management Science
- Ordering Working Papers
- Home page for this series
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 ().
RePEc:hhs:nhhfms:2015_004This page generated on 2024-11-12 04:36:04.