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.