  We consider 1-skeletons of the symmetric and asymmetric traveling salesperson
polytopes whose vertices are all possible Hamiltonian tours in the complete
directed or undirected graph, and the edges are geometric edges or
one-dimensional faces of the polytope. It is known that the question whether
two vertices of the symmetric or asymmetric traveling salesperson polytopes are
nonadjacent is NP-complete. A sufficient condition for nonadjacency can be
formulated as a combinatorial problem: if from the edges of two Hamiltonian
tours we can construct two complementary Hamiltonian tours, then the
corresponding vertices of the traveling salesperson polytope are not adjacent.
We consider a heuristic simulated annealing approach to solve this problem. It
is based on finding a vertex-disjoint cycle cover and a perfect matching. The
algorithm has a one-sided error: the answer "not adjacent" is always correct,
and was tested on random and pyramidal Hamiltonian tours.
