Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Attempting to find the optimal (exact) solution to TSP

  1. Aug 2, 2008 #1
    Hello - I'm attempting to find the optimal (exact) solution to the Traveling Salesman Problem in polynomial time using a Tabu search algorithm and Set theory. Currently my math skills ended with high-school calculus and some statistics in college, so the scope of analyzing mathematically the algorithm I have designed is beyond my level of knowledge (the algorithm was devised using more of a trial and error approach due to my lack of math skill).

    Specifically I am in need of individual(s) who specialize in the following:

    - Set Theory
    - Structured Query Language
    - Tuple relational calculus
    - Relational algebra
    - Combinatorics

    I have two specific questions at this time I need help with based on my algorithm:

    1. The algorithm I have outlined does not actually solve the traveling salesman problem in polynomial time, but rather is a polynomial-time approximation scheme (PTAS) or weakly polynomial run-time.

    2. The algorithm I have outlined does not solve the traveling salesman problem any faster than the known current exponential time O(n22n)) algorithms.

    3. The algorithm I have outlined does not always find the optimal (exact) solution, but rather is an approximation algorithm (Tabu search is this type of heuristic).

    Note: I don't need help with #3 at this time as this is way beyond the scope of being analyzed yet. Obviously if the the #1 and #2 questions are proven to be false then #3 can be pursued.

    I have a very strong assumption that one of the #1 - 3 questions will be proven to be true (hopefully for my peace of mind #1 or #2 will be proven to be true and then I don't need to pursue trying to solve this problem anymore).

    Anyway to keep this short the whole point of doing all of this is to attempt a proof that P = NP.

    If you can help with these questions I would be most appreciative. I would also be willing to pay/compensate you for your time or other individuals time to help me in answering the questions above as needed (within reason).

    I'm not affiliated with any University or have access to professors specializing in combinatorics. In addition this is personal project (I have had a lot of free time to work on this).

    I have already done all the research and documentation for the algorithm and back tested with three random data samples (2-16 point tours, and 1-18 point tour).

    The pdf document can be accessed from the link:


    Password: c8fgRX239mf

    This forum appears to have individuals with a very high-level of combinatorics experience that could help in analyzing this algorithm and be able to answer questions #1 and #2.

    I apologize if this is not the appropriate place to post/ask this question.

    Thank you very much for your time or any help you can provide!
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted

Similar Discussions: Attempting to find the optimal (exact) solution to TSP