working on a solution to the travelling salesman problem

Nov 2014
12
0
Moorhead M
Hello, I am currently working on a solution to the travelling salesmen time problem. However i need to test a lot of graphs. I was hoping that i could make this post and get assistance from my fellow mathletes.

so here is what i need:

I have the capacity to test up to a k11 using a brute force algorythm on my computer at the moment. So i need sample graphs to run through my brute force program and my method's program. So please, if people could post sample tables so that i basically have them generated while i am at work/school. This will save me time in the long run.

Also, I am looking for assistance with a presentation. I need a real scenario that a company/individual or whoever would have gone through using our current methods to solve for a larger graph. Such as a k50 or something. I know that we have methods of approximating and breaking down large graphs, and i was hoping that i could test my results against an actual problem that someone else has had to deal with. here are my constraints:

the chart must be symmetrical
the graph must be greater that K3 and less than a K12 (that is what i can currently test with brute force)

for the real life problem I also need a symmetrical chart, but i would like it to be big. bigger than we can solve using repeated nearest neighbor and the likes. something that we would have to use one of the more complex methods to approximate for. My goal is to apply my method and either tie it (which i believe means that they, and i, have found optimal) or undershoot its results (which i would believe that i had hit optimal).

Again, I am looking for a real world sample problem that has been used, and also the results that the corporation/individual used for their working solution. More likely than not, they did not find optimal, but found a close enough approximate.

Any assistance on this would be greatly appreciated.

Thanks in advance, Alex
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
There's a collection of instances here: TSP Test Data

But I don't see any that are small enough for your requirements, as I understand them.

State-of-the-art is 85,000 cities for an exact solution or millions of cities for an approximate (< 1% away from optimal) solution.
 
Last edited:

v8archie

Math Team
Dec 2013
7,710
2,679
Colombia
You can generate $k_{11}$ graphs easily, there are only $\frac12 n(n+1)= 66$ edges to generate with each with a random cost.
 
Nov 2014
12
0
Moorhead M
thank you!

Do you have a link for the state-of-the-art one? i would love to undercut its results, the program my partner and I are working on will be able to test one that large.
 

v8archie

Math Team
Dec 2013
7,710
2,679
Colombia
I imagine that the truly state-of-the-art solvers would be closely guarded proprietary systems, even if the methods used are published.
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
Do you have a link for the state-of-the-art one? i would love to undercut its results, the program my partner and I are working on will be able to test one that large.
http://www.math.uwaterloo.ca/tsp/pla85900/

You won't be able to undercut its results -- that's what "optimal" means. There's a several million-city TSP that's been solved to within 0.1%, though, and that you could (conceivably) undercut.
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
I imagine that the truly state-of-the-art solvers would be closely guarded proprietary systems, even if the methods used are published.
I wouldn't have thought so, but maybe. I know one of the authors, though, so I could ask if we really care.
 
Nov 2014
12
0
Moorhead M
undercutting

well here is the deal. I have possibly (I am very optimistic though) found a way to remove it from being an NP problem, and making it a situation of geometric (i think that is the term) growth instead of exponential. With a few rules (in the process of testing) I may have found a way to have the number of paths to test become n-1 where n is the size of the graph. the other outcome on the horizon is 2(n-1) possibilities. where as our current way of finding optimal is by brute force, my method would be both efficient and accurate. I am in the process of testing it still and trying to create proofs. But as a presentation I am looking for real world results that have been settled for. and .1% is great (especially considering the number of possible solutions), so If i were to find a result that would be lower, with a history of hitting optimal in smaller graphs (k4-k16 is my range of testing at the moment and currently hitting optimal in all cases), then I think that would be strong evidence that my method finds optimal consistently. obviously not a proof, but strong evidence.

so yes the odds of undercutting it is very very small, but that is what i need to do, undercut fantastic results by generating perfect results

so for instance, a k16 graph (1.3 trillion options) would only have to test 15 (or 30) paths.
 
Nov 2014
12
0
Moorhead M
http://www.math.uwaterloo.ca/tsp/pla85900/

You won't be able to undercut its results -- that's what "optimal" means. There's a several million-city TSP that's been solved to within 0.1%, though, and that you could (conceivably) undercut.
i would just need to get there graph list and their results, i wouldnt need the program. i found their results. i just need to find the table now