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: (Circle-Circle Intersection -- from Wolfram MathWorld)
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.
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.
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.
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!
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, FindShortestTour—Wolfram Documentation
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.
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.
“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.