A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems.

Padberg, M., & Rinaldi, G. (1991). A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review, 33(1), 60-100.

Type

Journal article

Intellectual base

Primary research

Year

1991

DOI

10.1137/1033004

Link

https://doi.org/10.1137/1033004

Cited from

operations_research

Cited by

2 citations across 2 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Branch and Bound
  • The subsequent development extended the framework to mixed-integer programming (Beale 1979, Benichou et al. 1971), introduced cutting-plane integration producing branch-and-cut (Padberg and Rinaldi 1991

    This sourcecanonical paper introducing the branch-and-cut variant (polyhedral cutting planes integrated with branch-and-bound) and its dramatic effect on solvable TSP sizes.

• Integer Linear Programming (ILP)
  • Major firms (UPS ORION routing, airline crew scheduling at Delta/American/Lufthansa, freight routing at CSX and BNSF) run large MIPs routinely on top of branch-and-cut machinery codified by Padberg and Rinaldi (1991).

    This sourceCanonical paper introducing the branch-and-cut variant—integrating polyhedral cutting-plane generation with branch-and-bound search—and demonstrating its dramatic effect on solvable TSP instance sizes.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:686f4017ef15 · see in the full table