ISSN:
1436-4646
Keywords:
Travelling salesman problem
;
problem formulations
;
convex polyhedral cones
;
polyhedra
;
affine transformations
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract A transformation technique is proposed that permits one to derive the linear description of the imageX of a polyhedronZ under an affine linear transformation from the (given) linear description ofZ. This result is used to analytically compare various formulations of the asymmetric travelling salesman problem to the standard formulation due to Dantzig, Fulkerson and Johnson which are all shown to be “weaker formulations” in a precise setting. We also apply this transformation technique to “symmetrize” formulations and show, in particular, that the symmetrization of the standard asymmetric formulation results into the standard one for the symmetric version of the travelling salesman problem.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01582894
Permalink