1
$\begingroup$

I have encountered a problem that is essentially the textbook statement of the Traveling Purchaser Problem. I don't know if this is the proper place to put this, if not then I will delete it.

Also a note is that while I have done some studying on my own of computer science, I did not have much formal education in it. I do have a reasonably strong math background though.

Now on to the background of the problem:

I know the Traveling Purchaser Problem is NP-Hard, and thus there is no optimal solution algorithm known. I know that as such, there are many different solution algorithms, of varying efficiency. The (admittedly few) papers that I have seen though use this on sets of 100s of nodes, and don't explicitly state the complexity of the algorithm in terms of big-O notation or similar functions. Since my data set is relatively small (7 nodes and about 50 items to purchase). I was wondering if it might be a waste of time to implement a complex, if efficient, algorithm. But that is not my question, as I think such questions would be out of place here, it is just the background.

My question is the following:

What are some of the common algorithms for approximating the solution to the Traveling Purchaser Problem along with their computational complexity in terms of the number of nodes and the number of items to purchase.

Improve this question
$\endgroup$
1
  • $\begingroup$ For 7 nodes, there are only 7! = 5040 possible full orders. I'm confident that just enumerating all of them with a tree search, keeping track of the cheapest price so far for each good that you need in the current partial solution, will solve this problem in under 1ms. $\endgroup$
    – j_random_hacker
    May 15, 2018 at 12:52

1 Answer 1

Reset to default
1
$\begingroup$

First, it is good to observe that the problem is very difficult to approximate (see e.g., my earlier answer on it here).

Second, there is very recent survey on the traveling purchaser problem and its variants by Manerba et al. [1]. Essentially, you will find discussion on relevant methods that have been applied to solve the problem in practical settings. If you want theoretical time bounds for heuristics, see Section 6.1.1. on page 13.

[1] Manerba, Daniele, Renata Mansini, and Jorge Riera-Ledesma. "The traveling purchaser problem and its variants." European Journal of Operational Research 259.1 (2017): 1-18.

Improve this answer
$\endgroup$

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.