Student or educator? Sign up with your school email and get 6 months of Pro free.
Cited by 294

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

Crowder, Harlan, Padberg, Manfred W.·1980·Management Science

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1287/mnsc.26.5.495

Cites

3 of 3 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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

Show all 3 references

Cited by

See all 294

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.