7

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.

Improve this question
10
  • 9
    For NP-hard, if you need an exact solution, you need to evaluate all possibilities and keep the best.
    – user1249
    Dec 4, 2011 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, 2011 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, 2011 at 9:39
  • This reference provides a pseudo code of the algorithm: Book-Transgenetic algorithm for the Traveling Purchaser Problem
    – NoChance
    Dec 4, 2011 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, 2011 at 11:39

3 Answers 3

Reset to default
16

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.

Improve this answer
3
  • Fixed some typos, but otherwise a perfect answer :-)
    – Dean Harding
    Dec 4, 2011 at 23:17
  • Thank you very much. Designing the test data backwards is really a good idea!
    – scravy
    Dec 5, 2011 at 9:45
  • 11
    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]
    – user4234
    Dec 5, 2011 at 12:17
1

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.

Improve this answer
1

Even if NP-hard, the TPP can be solved efficiently in practice by many different exact methods (as the TSP). Dynamic programming, Mathematical Programming (branch-and-cut, branch-and-bound), and Constraint Programming -based algorithms exist and have been proposed for the TPP in the Operation Research/Computer Science literature. I suggest you to read a very recent survey on the topic: "Manerba et al., 2017. The Traveling Purchaser Problem and its Variants, European Journal of operational Research 259, 1-18".

Of course, the practical complexity of solving exactly the TPP grows with the number of markets and products (especially the market). However, by using the proper methods, exact solutions can be found in a reasonable amount of time on modern computers for instances with 150/200 markets and 200/300 products.

Some known solvers (Cplex, Gurobi, ..) are also able to solve exactly some small/medium instances of the TPP if its model is given as input. This will be very useful if you need those solutions just for berchmarking your heuristics. In that case, the mathematical formulation of the problem is a critical issue to address.

PS: For the folklore, if you find an exact algorithm having a polynomial time complexity that solves a NP-hard problem, then you also solve the "P vs NP" open problem proposed by the Clay Institute as one of the Millenium Problems and win 1 million of dollars.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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