Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 3 down vote favorite
3

Which search/optimization problems can be reduced to the famous "Traveling Salesman Problem"? For instance, I have a collection of N particles, in 3D, and there is a function (Van der Waals energy) which depends on their coordinates. I want to find which configuration of the system minimizes the value of the function. Can this problem or type of problems by reduced to TSP? Could you point me to some bibliography?

PS: How could this problem be reduced to TSP?

share|improve this question
If you are looking for a technique that can be used to solve the TSP problem then one popular method is simulated annealing. It will give you the global minimum but is very expensive unless you can come up with a cheaper version of your problem (i.e., solve an approximate problem instead of the actual one). If your problem has a single minima then any gradient based method will work and will be much cheaper. Having said that, all global optimization problems involve searching for a global minima or maxima. In that sense all such problems are like the TSP. – stali Apr 20 '12 at 12:27
Is the function (and its derivatives) continuous? Are there any restrictions on how you select the N points? For example, can you select all N points at the global minimum? Do the N particles have to be located at distinct (x,y,z) points? – Paul♦ Apr 20 '12 at 13:23
It doesn't seem apparent to me that your problem is a variant of TSP... As @stali noted, your problem seems to be one of global optimization. Do you have any need to find the shortest path that connects to every point and returns to its point of origin? – Paul♦ Apr 20 '12 at 13:27
3  
The general procedure for determining if a problem is in the class of so-called NP problems is to prove bidirectional equivalency through polynomial transformations. It's a little hard to even guess whether this is possible without more information about the function you're considering. – Aron Ahmadia Apr 20 '12 at 15:46

2 Answers

up vote 4 down vote

Depending on which version of the Traveling Salesman Problem (TSP) you're looking at, it's either NP-hard (finding the shortest possible route), or NP-complete (called the decision version of TSP; given a length $L$, determine if any tour of a given graph has length less than or equal to $L$).

The difference between the two is subtle, but important: NP-hard problems are at least as hard as any problem in NP. The way you show a problem is at least as hard as another problem is to use what's called a reduction. A reduction is a way of transforming your given problem into the problem you'd like to compare it with. In this case, if you want to compare TSP to, say, a known NP problem like 3-SAT (satisfiability of a Boolean statement consisting of clauses containing 3 literals), you would try to reduce TSP to 3-SAT. The idea is to convert an instance of a problem $a$ that we don't yet know how to solve into a problem $b$ that we do know how to solve, such that the solution to $b$ can be used to determine a solution to $a$. Then, by converting $a$ to $b$ and solving $b$, we've constructed an algorithm to solve $a$. If we know how long the conversion process -- that is, the reduction -- takes, and we know how long it takes to solve problem $b$, then we can figure out an upper bound on how long it takes to solve the problem $a$.

The most common and useful kind of reduction I saw in my introductory graduate-level theory of computation course was called a polynomial-time reduction, which is a reduction process whose algorithm takes polynomial time, as a function of some metric of problem size, to produce its output. This concept is then used to define what NP-complete means. A problem $p$ is NP-complete if it is in NP, and for every problem in NP, there exists a polynomial-time reduction from that problem to problem $p$. NP-hard can be defined a similar way: a problem $p$ is NP-hard if there exists a polynomial time reduction from an NP-complete problem to $p$.

Now that all of that terminology is out of the way, to answer your question:

  • If you're talking about the NP-complete decision version of TSP, then any problem in NP can be reduced in polynomial time to TSP. Global optimization problems tend to be NP-hard (though I don't know for sure that all of them are, I do know that nonconvex optimization problem are NP-hard). Since NP-hard problems by definition are polynomial time reductions of NP-complete problems, TSP can be polynomial time reduced to NP-hard global optimization problems.
  • If you're talking about the NP-hard version of TSP, then no statements can be made about reductions of NP-hard global optimization problems.
  • There is nothing to suggest that NP-hard optimization problems can be reduced to either version of TSP. However, it is known that 0-1 integer programming is an NP-complete problem, so it can be reduced to TSP.

A good, but dense, reference is Michael Sipser's Introduction to the Theory of Computation, 2nd edition. (Disclaimer: Professor Sipser taught my theory of computation class.)

share|improve this answer
up vote 1 down vote

What you're trying to compute, if I understood your question correctly, is usually known as Lennard-Jones cluster minimization. A quick search in Google Scholar will give you a list of the most relevant publications on the topic.

Having worked on this problem myself years ago, I don't think that this can be modelled as a TSP. If you consider a path over all particles using the Lennard-Jones/Van der Waals potential as the distance measure, then, for each particle, only the energy to two other particles is taken into account, although it interacts with all neighbours. Furthermore, your interaction potential may permit negative values, leading to negative distances, which may cause problems for most TSP algorithms.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.