×
Padberg, M.; Rinaldi, G.

Optimization of a 532-city symmetric traveling salesman problem by branch and cut. (English) Zbl 0618.90082

Oper. Res. Lett. 6, 1-7 (1987).
We report the solution to optimality of a 532-city symmetric traveling salesman problem involving the optimization over 141 246 zero-one variables. The results of an earlier study by H. Crowder and M. Padberg [Manage. Sci. 26, 495-509 (1980; Zbl 0444.90068)] are cross- validated. In this note we briefly outline the methodology, algorithms and software system that we developed to obtain these results.

Cited in 1 Review
Cited in 77 Documents

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
65K05 Numerical mathematical programming methods

Keywords:

polyhedral methods; software design; branch and cut; 532-city symmetric traveling salesman

Citations:

Zbl 0444.90068
PDF BibTeX XML Cite
\textit{M. Padberg} and \textit{G. Rinaldi}, Oper. Res. Lett. 6, 1--7 (1987; Zbl 0618.90082)
Full Text: DOI

References:

[1] Crowder, H.; Padberg, M., Solving large-scale symmetric travelling salesman problems to optimality, Management Science, 26, 495-509 (1980) · Zbl 0444.90068
[2] Dantzig, G.; Fulkerson, R.; Johnson, S., Solution of a large-scale traveling salesman problem, Operations Research, 2, 393-410 (1954) · Zbl 1414.90372
[3] Dantzig, G.; Fulkerson, R.; Johnson, S., On a linear programming combinatorial approach to the traveling salesman problem, Operations Research, 7, 58-66 (1959) · Zbl 1414.90211
[4] Grötschel, M., On the symmetric travelling salesman problem: Solution of 120-city problem, Mathematical Programming Studies, 12, 61-77 (1980) · Zbl 0435.90070
[5] Grötschel, M.; Padberg, M., Polyhedral theory, (Lawler, E.; etal., The Travelling Salesman Problem (1985), Wiley: Wiley Chichester), 251-305 · Zbl 0587.90073
[6] Held, M.; Karp, R., The traveling salesman problem and minimum spanning trees: Part II, Mathematical Programming, 1, 6-26 (1971) · Zbl 0232.90038
[7] Lin, S.; Kernighan, B., An effective heuristic algorithm for the traveling salesman problem, Operations Research, 21, 498-516 (1973) · Zbl 0256.90038
[8] Marsten, R., The design of the XMP linear programming libary, ACM Transactions of Mathematical Software, 7, 481-497 (1981)
[9] Padberg, M.; Grötschel, M., Polyhedral computations, (Lawler, E.; etal., The Traveling Salesman Problem (1985), Wiley: Wiley Chichester), 307-360 · Zbl 0587.90074
[10] Padberg, M.; Hong, S., On the symmetric traveling salesman problem: A computational study, Mathematical Programming Studies, 12, 78-107 (1980) · Zbl 0435.90071
[12] Rinaldi, G.; Padberg, M., An efficient algorithm for the minimum capacity cut problem in large sparse graphs (1985), IASI-CNR: IASI-CNR Rome, Preprint
[13] Rinaldi, G.; Yarrow, L. A., Optimizing a 48-city traveling salesman problem: A case study in combinatorial problem solving (1985), IASI-CNR: IASI-CNR Rome, Preprint R.122
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.