Message Boards Message Boards

0
|
2644 Views
|
7 Replies
|
1 Total Likes
View groups...
Share
Share this post:

TSP Geometry conjecture

Posted 8 years ago

Why discuss this with the Wolfram community Wolfram provides one of the best known optimal TSP solving Algorithms. Wolfram also provides an abundance of data handling and visualization tools to investigate ways to improve the search for the optimal TSP.

Background: TSP (Traveling Salesman Problem) Algorithms are fed a matrix of costs from each point to every other point. To be specific I am discussing symmetrical, and triangle inequality compliant sets of data (and any other requirements that means the data can be plotted in 2 dimensions such as as the bird flies distances between locations) I am also specifically focused on the optimal solution not a heuristic for nearly optimal solution. Forgive my inexperience on this topic and the appropriate terminology to use, in my defense the title states this is conjecture.

Most lectures on the topic visualize the data as points with lines connecting them.
But the process and algorithms rely strictly on the cost matrix. Even TSP LIB provides data for x and y values of each point for visualization of the problem yet states in their documentation that the these will cause inaccurate results if used. In my opinion the cost matrix is a fairly 1 dimensional view of the problem.

My Idea I think there is a lot to be gained by relying on geometrical truths found in a 2D approach to the problem.

There should be an algorithm somewhere for converting a cost matrix to points. cost is the distance between the points (perhaps that is a bit specific, but i have had trouble finding such an algorithm) Does anyone know if Wolfram already provides a tool for this? if not perhaps we could work together to add it as an extension.

conditions of a cost matrix to 2d points algorithm: the algorithm could be tested by converting to points and using then using the distance between each point to convert back to a cost matrix (with some forgiveness for floating point errors) you could also start with points to make a test cost matrix and back again to visually test such an algorithm. The results should be expected to be flipped and or rotated compared to the input, which is perfectly fine for the intended purpose.

a high level view of the cost matrix to 2d points algorithm: 1st point is always at x=0, y=0; (if 2nd point is too close to 1st point i worry it could cause confusion with floating point error) 2nd point is x=[0][0] y=0; //[0][0] is the cost between the 1st and 2nd point 3rd point: (if 3rd point is co-linear with 1st point and 2nd point, choose a different 3rd point, if all points are co-linear with 1st and 2nd point then your TSP is probably simply solved) uses circle intersect formula of: (http://mathworld.wolfram.com/Circle-CircleIntersection.html) 1st point with its radius equal to the cost between 1st point and 3rd point 2nd point with its radius equal to the cost between 2nd point and 3rd point there are 2 points where the circles intersect either of them is valid for the 3rd point nth point is solved the same way as 3rd point except the 3rd point is used to decide which of the 2 circle intersect points are valid.

I will start other discussions soon for how i think this can help improve TSP algorithms. I would like this discussion to focus on the validity of the conjecture that cost matrix can be reliably converted into a 2D set of points for qualifying TSP data sets.

Also please let me know if someone is already doing this.

POSTED BY: Brian Davis
7 Replies
Posted 8 years ago

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.

POSTED BY: Brian Davis

As best I can tell you want to take a matrix of valid planar distances and recover a set of points whose pairwise distances recover that matrix. This can be done using singular value decomposition. Details and Mathematica/WL code may be found in this recent TMJ article.

POSTED BY: Daniel Lichtblau
Posted 8 years ago

Wonderful and relevant article thank you very much for this! MDS is an existing method for converting the data I described into 2D points. It seems they have some margin of error, and i wonder how a circle intersect solution (something like what i proposed in the original post) would compare on accuracy and performance.

Anyway, it looks like MDS is built into Mathematica/WL already, that is terrific!

POSTED BY: Brian Davis

In this instance I think it is the PCA approach that would be of greater use. Assuming the distances came from actual points in a plane, one can use PCA to recover the relative placement of the points, that is, it will be correct up to translation and rotation/reflection.

POSTED BY: Daniel Lichtblau
Posted 8 years ago

PCA is a fairly common acronym so I would like to mention this link in the discussion to provide reference to PCA in this context: https://en.wikipedia.org/wiki/Principalcomponentanalysis

also a helpful quote from that link:

"Mathematica – Implements principal component analysis with the PrincipalComponents command using both covariance and correlation methods."

@Daniel Lichtblau: "it will be correct [with the exception of] translation and rotation/reflection." That is exactly what I am looking for, thank you again. Also thanks for this clarification about the accuracy of PCA, it was difficult to discern that fact from the article I read.

POSTED BY: Brian Davis

Dear @Brian Davis what relation does your question have to Wolfram Technologies?

This forum permits only subjects related to Wolfram Technologies. Post elsewhere for other subjects or make clear the connection to Wolfram Technologies. Please read the guidelines.

POSTED BY: Moderation Team
Posted 8 years ago

Thank you, I have updated my post to be more compliant.

POSTED BY: Brian Davis
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract