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

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.


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


Zbl 0444.90068
Full Text: DOI


[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, (), 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, (), 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
[11] M. Padberg and G. Rinaldi, “An LP-based algorithm for the resolution of large-scale traveling salesman problems”, Preprint, New York University, New York, in preparation. · Zbl 0734.90060
[12] Rinaldi, G.; Padberg, M., An efficient algorithm for the minimum capacity cut problem in large sparse graphs, (1985), 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 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.