ISSN:
1436-4646
Keywords:
Traveling salesman problem
;
Lagrangian multipliers
;
Branch and bound
;
Lagrangian duality
;
Subgradient optimization
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract In this study we formulate the dual of the traveling salesman problem, which extends in a natural way the dual problem of Held and Karp to the nonsymmetric case. The dual problem is solved by a subgradient optimization technique. A branch and bound scheme with stepped fathoming is then used to find optimal and suboptimal tours. Computational experience for the algorithm is presented.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01584338
Permalink