Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem

Gerard Sierksma

Applicationes Mathematicae (1994)

  • Volume: 22, Issue: 3, page 351-358
  • ISSN: 1233-7234

Abstract

top
The 3-Opt procedure deals with interchanging three edges of a tour with three edges not on that tour. For n≥6, the 3-Interchange Graph is a graph on 1/2(n-1)! vertices, corresponding to the hamiltonian tours in K_n; two vertices are adjacent iff the corresponding hamiltonian tours differ in an interchange of 3 edges; i.e. the tours differ in a single 3-Opt step. It is shown that the 3-Interchange Graph is a hamiltonian subgraph of the Symmetric Traveling Salesman Polytope. Upper bounds are derived for the diameters of the 3-Interchange Graph and the union of the 2- and the 3-Interchange Graphs. Finally, some new adjacency properties for the Asymmetric Traveling Salesman Polytope and the Assignment Polytope are given.

How to cite

top

Sierksma, Gerard. "Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem." Applicationes Mathematicae 22.3 (1994): 351-358. <http://eudml.org/doc/219101>.

@article{Sierksma1994,
abstract = {The 3-Opt procedure deals with interchanging three edges of a tour with three edges not on that tour. For n≥6, the 3-Interchange Graph is a graph on 1/2(n-1)! vertices, corresponding to the hamiltonian tours in K\_n; two vertices are adjacent iff the corresponding hamiltonian tours differ in an interchange of 3 edges; i.e. the tours differ in a single 3-Opt step. It is shown that the 3-Interchange Graph is a hamiltonian subgraph of the Symmetric Traveling Salesman Polytope. Upper bounds are derived for the diameters of the 3-Interchange Graph and the union of the 2- and the 3-Interchange Graphs. Finally, some new adjacency properties for the Asymmetric Traveling Salesman Polytope and the Assignment Polytope are given.},
author = {Sierksma, Gerard},
journal = {Applicationes Mathematicae},
keywords = {Assignment Polytope; Traveling Salesman Polytope; Hamiltonian tours; symmetric traveling salesman polytope},
language = {eng},
number = {3},
pages = {351-358},
title = {Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem},
url = {http://eudml.org/doc/219101},
volume = {22},
year = {1994},
}

TY - JOUR
AU - Sierksma, Gerard
TI - Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem
JO - Applicationes Mathematicae
PY - 1994
VL - 22
IS - 3
SP - 351
EP - 358
AB - The 3-Opt procedure deals with interchanging three edges of a tour with three edges not on that tour. For n≥6, the 3-Interchange Graph is a graph on 1/2(n-1)! vertices, corresponding to the hamiltonian tours in K_n; two vertices are adjacent iff the corresponding hamiltonian tours differ in an interchange of 3 edges; i.e. the tours differ in a single 3-Opt step. It is shown that the 3-Interchange Graph is a hamiltonian subgraph of the Symmetric Traveling Salesman Polytope. Upper bounds are derived for the diameters of the 3-Interchange Graph and the union of the 2- and the 3-Interchange Graphs. Finally, some new adjacency properties for the Asymmetric Traveling Salesman Polytope and the Assignment Polytope are given.
LA - eng
KW - Assignment Polytope; Traveling Salesman Polytope; Hamiltonian tours; symmetric traveling salesman polytope
UR - http://eudml.org/doc/219101
ER -

References

top
  1. [1] A. Adrabiński and M. M. Sysło, Computational experiments with some approximation algorithms for the travelling salesman problem, Zastos. Mat. 18 (1) (1983), 91-95. Zbl0525.90095
  2. [2] M. Grötschel and M. W. Padberg, Polyhedral theory, in: The Traveling Salesman Problem, E. L. Lawler et al. (eds.), Wiley, 1985, 307-360. 
  3. [3] D. Hausmann, Adjacency in Combinatorial Optimization, Hain, Heisenheim am Glan, 1980. Zbl0439.90050
  4. [4] J. K. Lenstra, Sequencing by Enumerative Methods, Math. Center Tracts 69, Amsterdam, 1977. 
  5. [5] D. Naddef and W. R. Pulleyblank, Hamiltonicity and combinatorial polyhedra, J. Combin. Theory Ser. B 31 (1981), 297-312. Zbl0449.05042
  6. [6] D. Naddef and W. R. Pulleyblank, Hamiltonicity in (0-1)-polyhedra, ibid. 37 (1984), 41-52. Zbl0544.05058
  7. [7] M. W. Padberg and M. R. Rao, The travelling salesman problem and a class of polyhedra of diameter two, Math. Programming 7 (1974), 32-45. Zbl0318.90042
  8. [8] M. R. Rao, Adjacency of the travelling salesman tours and 0-1 vertices, SIAM J. Appl. Math. 30 (1976), 191-198. Zbl0346.90065
  9. [9] G. Sierksma, The skeleton of the Symmetric Traveling Salesman Polytope, Discrete Appl. Math. 43 (1993), 63-74. Zbl0818.05059
  10. [10] G. Sierksma, Adjacency properties of the Symmetric TSP Polytope, Res. Mem. 464, Inst. of Econ. Res., Univ. of Groningen, 1993. Zbl0818.05059
  11. [11] G. Sierksma and G. A. Tijssen, Faces with large diameter on the Symmetric Traveling Salesman Polytope, Oper. Res. Lett. 12 (1992), 73-77. Zbl0762.90083
  12. [12] I. Tomescu, Problems in Combinatorics and Graph Theory, Wiley, 1985. Zbl0561.05001

NotesEmbed ?

top

You must be logged in to post comments.