Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 4 down vote favorite
1

do you know of any algorithms which give an exact solution for the Traveling Purchaser Problem. I can only find heuristic and probabilistic approaches.

I do have implemented a genetic algorithm so far, which by its nature does not terminate by itself an does not always yield the optimal result. Thus I'm looking for an exact solution to the problem such that I'm able to compare my solution to an exact / optimal value for a given test data set.

For those of you who haven't heard of the Traveling Purchaser Problem (TPP), this is not the Traveling Salesman Problem (TSP), but a generalization of it. It thus is also NP-hard.

share|improve this question
8  
For NP-hard, if you need an exact solution, you need to evaluate all possibilities and keep the best. – user1249 Dec 4 '11 at 9:33
1  
I was thinking of that, but this sounds very “brute forcish”. I hoped there was maybe some known algorithm to exactly solve the problem like for TSP - there exists the Held–Karp algorithm, various branch-and-bound / branch-and-cut algorithms ... – scravy Dec 4 '11 at 9:37
5  
For generic NP-hard you cannot short-circuit if you want the exact solution. Sorry. Any short-cutting requires additional restrictions to the generic problem. – user1249 Dec 4 '11 at 9:39
This reference provides a pseudo code of the algorithm: Book-Transgenetic algorithm for the Traveling Purchaser Problem – Emmad Kareem Dec 4 '11 at 9:50
4  
NP-hard pretty much means that (as far as we know) a correct solution amounts to trying everything. It might make for a short, perhaps even elegant program, but certainly not a practicable one. – Kilian Foth Dec 4 '11 at 11:39
show 5 more comments

2 Answers

up vote 10 down vote accepted

The NP-Hard domain of problems means that, as far as current mathematical knowledge goes, the problem can only be solved by trying every permutation and choosing the correct answer.

If you can solve the problem more efficiently than the brute force method, you will win a Noble Prize in mathematics as a bonus. The best mathematicians have been working on a general answer to this problem for decades.

Perhaps as you are wanting to create a test data-set for your NP-Hard problem solver, your approach may be to design the test data backwards - rather than solve the NP-Hard problem, create an NP-Hard problem with a known answer - I don't even know if that is a NP-Hard problem on it's own.

share|improve this answer
Fixed some typos, but otherwise a perfect answer :-) – Dean Harding Dec 4 '11 at 23:17
Thank you very much. Designing the test data backwards is really a good idea! – scravy Dec 5 '11 at 9:45
6  
There is no Noble (or Nobel) prize in mathematics - the prize for physics would arguable be the closest Nobel award, or alternatively the Fields medal would be the closest equivalent. [/nitpick] – Mark Bannister Dec 5 '11 at 12:17
up vote 1 down vote

You may try integer linear programming, but I can give you only travelling salesman formulation, but it should not be difficult to modify, once you gat the idea. Other option can be to use some constraint programming library (such as JaCoP: http://www.jacop.eu/). In my experience it is possible to solve NP-hard problems with several hundred nodes using normal desktop computer. If you data is bigger, than you will have to use some approximation/genetic programming and things like that, you will not be able to get the exact solution.

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.