ISSN:
1436-4646
Keywords:
05C04
;
05C45
;
90C10
;
Travelling salesman problem
;
cutting plane algorithms
;
polyhedral combinatorics
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract In this paper we report on a cutting plane procedure with which we solved symmetric travelling salesman problems of up to 1000 cities to optimality. Our implementation is based on a fast LP-solver (IBM's MPSX) and makes effective use of polyhedral results on the symmetric travelling salesman polytope. We describe the important ingredients of our code and give an extensive documentation of its computational performance.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01586932
Permalink