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 ReviewCited in 78 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 × Cite Format Result Cite Review PDF 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 [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.; 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: 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.