TSP Geometry conjecture: No crossed paths assertion.
not sure if it would be preferred to start another post, this is more or less a continuation of the same topic, and requires 2D points
I found my self asking the same question asked here, and they link to a good article on the topic.
http://stackoverflow.com/questions/2444125/crossing-edges-in-the-travelling-salesman-problem
the article:
http://www.ams.org/samplings/feature-column/fcarc-tsp
figure 5 shows that some edges can be excluded from the matrix that would be sent to the branch and bound algorithm.
some edges would always cause a crossed edge, for example if you were to find the convex hull of all the points, and the hull connected a-b, b-c, c-d, d-e then you can safely assert that a will never go to c because it would always cause a crossed edge for anything else to get to b, that does not mean that a will go to b, just that it will not go to c, so a-c can be pruned from the matrix.
but there are also edges that are merely mutually exclusive, as such they cannot be removed from the matrix entirely.
for example: if F-G is known the cross H-I, then once the F-G is only pruned when H-I is part of the route, and vice versa, but both are possible options while neither is part of the route.
In wolfram's TSP solver, http://reference.wolfram.com/language/ref/FindShortestTour.html#114665653
does Wolfram already handle this internally? (is there a way to see the source to know what wolfram already accounts for?)
if not:
is there a way to denote which parts of the matrix are mutually exclusive?
if not:
I suspect my best bet would be to permutate the mutual exclusions into a (potentially large) set of matrices to solve that each have some of the mutually exclusive edges pruned out from the list of possible paths.
