Abstract
We describe an algorithm for the asymmetric traveling salesman problem (TSP) using a new, restricted Lagrangean relaxation based on the assignment problem (AP). The Lagrange multipliers are constrained so as to guarantee the continued optimality of the initial AP solution, thus eliminating the need for repeatedly solving AP in the process of computing multipliers. We give several polynomially bounded procedures for generating valid inequalities and taking them into the Lagrangean function with a positive multiplier without violating the constraints, so as to strengthen the current lower bound. Upper bounds are generated by a fast tour-building heuristic. When the bound-strengthening techniques are exhausted without matching the upper with the lower bound, we branch by using two different rules, according to the situation: the usual subtour breaking disjunction, and a new disjunction based on conditional bounds. We discuss computational experience on 120 randomly generated asymmetric TSP's with up to 325 cities, the maximum time used for any single problem being 82 seconds. This is a considerable improvement upon earlier methods. Though the algorithm discussed here is for the asymmetric TSP, the approach can be adapted to the symmetric TSP by using the 2-matching problem instead of AP.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. Balas, “Cutting planes from conditional bounds: A new approach to set covering”,Mathematical Programming Studies 12 (1980) 19–36.
E. Balas and N. Christofides, “A new penalty method for the traveling salesman problem”, Paper presented at the Ninth International Symposium on Mathematical Programming, Budapest, August 1976.
M. Bellmore and J.C. Malone, “Pathology of traveling salesman subtour elimination algorithms”,Operations Research 19 (1971) 278–307.
M. Bellmore and G.L. Nemhauser, “The traveling salesman problem: A survey”,Operations Research 16 (1968) 538–558.
R.E. Burkard, “Traveling salesman and assignment problems: A survey”,Annals of Discrete Mathematics 4 (1979) 193–217.
N. Christofides, “The shortest hamiltonian chain of a graph”,SIAM Journal of Applied Mathematics 19 (1970) 689–696.
N. Christofides, “Bounds for the traveling salesman problem”,Operations Research 20 (1972) 1044–1055.
N. Christofides,Graph theory: An algorithmic approach (Academic Press, New York, 1976).
N. Christofides, “The traveling salesman problem”, in: N. Christofides, A. Mingozzi, P. Toth and C. Sandi,Combinatorial Optimization (Wiley, New York, 1979) pp. 131–150.
G.B. Dantzig, D.R. Fulkerson and S. Johnson, “Solution of a large scale traveling salesman problem”,Operations Research 2 (1954) 393–410.
W.L. Eastman, “Linear programming with pattern constraints”, Unpublished Ph.D. Dissertation, Harvard University, 1958.
K.H. Hansen and J. Krarup, “Improvements of the Held—Karp algorithm for the symmetric traveling salesman problem”,Mathematical Programming 7 (1974) 87–96.
M. Held and R. Karp, “The traveling salesman problem and minimum spanning trees”,Operations Research 18 (1970) 1138–1162.
M. Held and R. Karp, “The traveling salesman problem and minimum spanning trees, II”,Mathematical Programming 1 (1971) 6–25.
V. Klee, “Combinatorial optimization: What is the state of the art”,Mathematics of Operations Research 5 (1980) 1–26.
H. Kubo and N. Okino, “A new practical solution for large traveling salesman problems”,Journal of the Operations Research Society of Japan 19 (1976) 272–285 [In Japanese.]
D.M. Shapiro, “Algorithms for the solution of the optimal cost and bottleneck traveling salesman problem”, Unpublished Sc.D. Thesis, Washington University, St. Louis, 1966.
T.C.H. Smith and G.L. Thompson, “Computational performance of three subtour elimination algorithms for asymmetric traveling salesman problems”,Annals of Discrete Mathematics 1 (1977) 495–506.
Computer Review, GML Corp., Lexington, MA (1979).
Author information
Authors and Affiliations
Additional information
Research supported by the National Science Foundation through grant no. MCS76-12026 A02 and the U.S. Office of Naval Research through contract no. N0014-75-C-0621 NR 047-048.
Rights and permissions
About this article
Cite this article
Balas, E., Christofides, N. A restricted Lagrangean approach to the traveling salesman problem. Mathematical Programming 21, 19–46 (1981). https://doi.org/10.1007/BF01584228
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01584228