The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
Abstract
We report the solution to optimality of ten large-scale symmetric travelling salesman problems. The travelling salesman problem (TSP) is one of the standard problems of the Operations Research/Management Science literature and is cited in virtually every textbook on this subject. The TSP is a hard combinatorial optimization problem for which to date no technically good algorithm is known. All known algorithmic approaches to the TSP that are amenable to a worst-case analysis have yielded nothing for this problem that is as satisfactory as the existing solution procedures for, as an example, flow problems in networks. Furthermore, recent theoretical work has shown that the TSP is algorithmically equivalent to the general zero-one decision problem with linear constraints and objective function. The phrase “This problem is as hard as a travelling salesman problem” reflects this fact and expresses the slim chances of finding an optimal solution to the problem at hand. It is therefore all the more surprising that in the current study, all of the test problems were solved to optimality—i.e., the proposed methodology did not fail on any one of the ten large-scale test problems of the computational study. Besides being a prototype of a difficult combinatorial optimization problem, the travelling salesman problem has a variety of applications in its own right, mostly in the areas of production management, vehicle routing, and vehicle scheduling. A number of related problems, such as, for example, the multiple travelling salesman problem with m travelling salesmen located at a central depot and with fixed charges for their deployment, have been shown elsewhere to fit the standard form of the TSP treated in this paper. The smallest problem of this computational study has 48 cities and the largest one has 318 cities, i.e., the corresponding zero-one linear programming problems have between 1,128 and 50,403 zero-one variables. The algorithmic procedure is a cutting-plane approach coupled with branch-and-bound. For the latter we use the IBM software system MPSX-MIP/370 in a novel (iterative) way. The cutting-planes that we use are subtour-elimination and comb constraints, i.e., they belong to the class of valid inequalities for the symmetric travelling salesman problem which define facets for the associated polytope. This fact, which has been proven mathematically elsewhere, makes the cutting-planes encountered here different from other arbitrary, but valid, cutting-planes encountered in integer programming. In fact, cutting-planes have been virtually abandoned as an algorithmic tool in integer programming because of the erratic behavior of such algorithms exhibited in earlier computational studies. The present study convincingly establishes the usefulness of mathematically proven good cutting-planes as an invaluable algorithmic tool for difficult combinatorial optimization problems. Here the word optimization is taken in its very meaning—we are interested solely in finding a solution that minimizes a cost function and in proving it to be an optimal solution.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An Effective Heuristic Algorithm for the Traveling-Salesman Problem
Lin, S., & Kernighan, B. W. (1973) · Operations Research · doi:10.1287/opre.21.2.498 · Cited by 3,821
Maximum matching and a polyhedron with 0,1-vertices
Edmonds, J. (1965) · Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics · doi:10.6028/jres.069b.013 · Cited by 1,712
A Heuristic Approach to Solving Travelling Salesman Problems
Karg, R. L., & Thompson, G. L. (1964) · Management Science · doi:10.1287/mnsc.10.2.225 · Cited by 210
Cited by
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134
Sherali, H. D., & Adams, W. P. (1990) · SIAM Journal on Discrete Mathematics · doi:10.1137/0403036 · Cited by 931
Metadata
- Authors
- Crowder, H., & Padberg, M. W.
- Venue
- Management Science
- Published
- 1980-05
- Volume
- 26
- Issue
- 5
- Pages
- 495-509
- ISSN
- 0025-1909 (ISSN-L)
- 1526-5501
- OpenAlex
- W2114552889
- Cited by
- 294
- References
- 3
- FWCI
- 54.86
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality. https://app.cochat.ai/papers/10.1287/mnsc.26.5.495
- The paper
- Crowder, H., & Padberg, M. W. (1980). Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality. Management Science. https://doi.org/10.1287/mnsc.26.5.495
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.