Combinatorial Optimization - Directed Graphs

[chrisaaker]

I am using a brute force approach to solve a version of the traveling salesman problem. I am looking into ways to optimize it but there are many. Basically I need help further defining the problem and how to solve it optimally.

 

Given

 

[path] [start city] [end city] [distance]

 

P1 C1 C2 100

P2 C2 C1 400

P3 C1 C3 300

P4 C3 C1 200

P5 C2 C3 100

P6 C3 C2 400

 

Determine the shortest path which tours all the cites. Currently i check all possibilities using all combinations nCk where n = 6 and 3 <= k <= 6, filter these solutions to make sure all cities can be reached and finally choose the one with the lowest cost.

 

Thanks

[imatfaal]

That's one hell of a one-way-system you have there - 4 times longer to return from C2->C1 than the outbound journey C1->C2. The travelling salesman problem does not canonically have different distances for outbound and inbound to a city (ie it forms a symmetric graph) , and also cities are only visited once; but I presume that these are new parts of the version you are looking at.

 

the very point TSP is discussed is that it is prototypically np - that means that the solution time does not scale polynomially with the number of variables. I don't believe that removing the symmetry or the proviso tha cities are only visited once will stop the problem being NP-hard. The canonical version does have algorithms that can help - search on Nikos Christofides - his algorithm algorithm will get you within 50% of the actual best distance.

 

The permutation method that you are looking at scales in the order of n! 30 cities would require over 10^34 operations.

 

For your guidance a solution that solves TSP in polynomial time would get you, at least, a million bucks in prize money

[DrRocket]

That's one hell of a one-way-system you have there - 4 times longer to return from C2->C1 than the outbound journey C1->C2. The travelling salesman problem does not canonically have different distances for outbound and inbound to a city (ie it forms a symmetric graph) , and also cities are only visited once; but I presume that these are new parts of the version you are looking at.

 

the very point TSP is discussed is that it is prototypically np - that means that the solution time does not scale polynomially with the number of variables. I don't believe that removing the symmetry or the proviso tha cities are only visited once will stop the problem being NP-hard. The canonical version does have algorithms that can help - search on Nikos Christofides - his algorithm algorithm will get you within 50% of the actual best distance.

 

The permutation method that you are looking at scales in the order of n! 30 cities would require over 10^34 operations.

 

For your guidance a solution that solves TSP in polynomial time would get you, at least, a million bucks in prize money

 

The traveling salesman problem is in fact NP-complete, so finding a fast algorithm comes under the heading of "really hard'. (Add as many "really"s as you like).

[imatfaal]

DocRock - of course you're correct.

 

As a corollary; has there been any further talk of Romanov's claim of solution to 3-SAT. I saw quite a lot about it at the beginning of this year in the popular science press, but very quickly it disappeared from view. I realise that it had to be very rigorously checked, do you happen to know if this process is still on going or that it was found to be lacking very quickly and died quietly? The mathematicians I read on the subject at the time were pretty certain it would be found to be incomplete and that the paper was poorly presented/on tenuous logical ground - but still felt that it merited proper research. I wonder if the academic maths press (which I do not read/ could not understand) have published any news.

 

Vladimir Romanov has released source code for an algorithm which he claims can solve 3-SAT problems. The 3-SAT problem is NP-complete - and Romanov claims his algorithm will solve in polynomial time, this would prove that P==NP as all NP problems can be mapped within polynomial time to the satisfiability problem.

 

With such a seemingly easily falsifiable claim Romanov might be proved wrong quite quickly - for any with the maths and compsci skill here is Romanov's announcement and links to the source code and article - and for those who need a bit more background here is a link to a long slashdot ramble that has some good stuff in it

Edited May 4, 2011 by imatfaal

[DrRocket]

DocRock - of course you're correct.

 

As a corollary; has there been any further talk of Romanov's claim of solution to 3-SAT. I saw quite a lot about it at the beginning of this year in the popular science press, but very quickly it disappeared from view. I realise that it had to be very rigorously checked, do you happen to know if this process is still on going or that it was found to be lacking very quickly and died quietly? The mathematicians I read on the subject at the time were pretty certain it would be found to be incomplete and that the paper was poorly presented/on tenuous logical ground - but still felt that it merited proper research. I wonder if the academic maths press (which I do not read/ could not understand) have published any news.

 

 

 

Apparently there are some problems with Romanov's initial claim.

 

http://www.computer.org/portal/web/news/home/-/blogs/3-sat-solution-flawed

[imatfaal]

Apparently there are some problems with Romanov's initial claim.

 

http://www.computer....solution-flawed

 

Thanks.