Solution of large-scale symmetric travelling salesman problems

In this paper the authors report on a cutting plane procedure with which they solve symmetric travelling salesman problems of up to 1000 cities to optimality. The present implementation is based on a fast LP-solver (IBM’s MPSX) and makes effective use of polyhedral results on the symmetric travelling salesman polytope. The authors describe the important ingredients of the code and give an extensive documentation of its computational performance.