Article ID: | iaor20022017 |
Country: | Netherlands |
Volume: | 29 |
Issue: | 3 |
Start Page Number: | 129 |
End Page Number: | 139 |
Publication Date: | Oct 2001 |
Journal: | Operations Research Letters |
Authors: | Arthanari T.S., Usha M. |
Arthanari proposed a Multistage-insertion (MI)-formulation of the symmetric traveling salesman problem (STSP). This formulation has a polynomial number of constraints. Carr proposed the Cycle-shrink relaxation of the STSP. In this paper, we show that there exists a natural transformation which establishes a one-to-one correspondence between the variables of the two formulations, say