On the equivalence of the multistage-insertion and cycle-shrink formulations of the symmetric traveling salesman problem

On the equivalence of the multistage-insertion and cycle-shrink formulations of the symmetric traveling salesman problem

0.00 Avg rating0 Votes
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: ,
Abstract:

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 X and U, such that X is feasible for MI-formulation if and only if U is feasible for the other. The size of the Cycle-shrink formulation is larger than that of the MI-formulation, both in the number of variables and constraints. However, both are compact descriptions of the subtour elimination polytope.

Reviews

Required fields are marked *. Your email address will not be published.