Algorithm to find optimal combination of products and shops to minimise cost

Question

Hello there Stackoverflow people,

I run a site that finds its users the cheapest place to buy books. This is easy for a single book, but for multiple books it can sometimes be cheaper to purchase one book at one store and another book from another store.

Currently I find the cheapest store that sells all books in the user's list, but I want to have a smarter system. Here's some more info:

• The price of a book is constant for a store.
• The price of shipping can vary, depending on # of books or the total value of the books.
• Each shop object can take an array of books and return the shipping cost.
• Frequently, not every shop sells every book.

Not sure if it's cool to link to my site here, but it is listed in my user profile.

I would like to be able to find the cheapest combination of stores and books.

I fear it requires a brute force approach - and with 35 shops, the number of combinations will be enormous for a modest number of books. I have a feeling the number of combination is (#shops)^(#books) - but not 100%

The question is, what approach should I use? Does this problem fit in a well known class of problems? If brute force is required, what's a good way of doing this in Ruby and can I prioritise shops to try first?

Mcalpin

Answer 1

Unfortunately this is an example of a combinatorial optimization problem that doesn't have any easy solution. You're right that you actually do, in general, need a brute force approach. However! I suspect there's some special structure in this problem that will help. For example, the cost of shipping will not change randomly as you change the combination of books - it will probably increase sub-linearly and/or saturate as you add books.

Here's what I recommend, then:

1. Offline, estimate the shipping policies of each shop, so that, given books (and perhaps their weights) you can estimate the cost of shipping without referring to their sites.
2. For each store, calculate how much each book would cost, if available.
3. Offline, go through each shop, or set of shops, and estimate, using your offline shipping policies, how much the total will cost.
4. Choose the shop (or shops) with the cheapest cost. If there are multiple that are similar, calculate the exact answer.

That should get you started, and will keep you short of a full search.

Colman

Hi - thanks for the response. 1-3 are already in place. A per-shop method is used to determine the shipping cost. One of the difficulties is that shipping value can be determined by number of books, or total price of order - which makes life a bit complex. Determining which single shop ships all books for the lowest cost is easy - it's figuring out that one of the books should be purchased at shop A, whilst the rest from shop B. – Mcalpin

Answer 2

This is a variation on what's classically called the "Assignment Problem". The classical AP has a few standard solutions, including the Munkres (aka "Hungarian") algorithm, and the JVC (Junker Volgenant Castanon iirc) algorithm.

The basic idea is to compute a cost for each assignment (that is, the cost of buying each book at each store), then select the set of assignments that minimize the total cost. This can be done in polynomial time, I believe.

The fact that the shipping cost from each retailer is dependent on the total order makes things considerably trickier. You might be able to use a hybrid approach that doesn't consider shipping costs originally, then does for aggregate orders once you've identified a few promising assignments.

Good luck, sounds like a fun problem!

Upstairs

Answer 3

Try using dynamic programming approach. You can read about it here: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg Also you can read about it on wikipedia or in "Introduction to Algorithms" book (Cormen).

It is quite standard problem.

Lobule

Answer 4

Brute Force can almost always be replaced by a good heuristic, that is, an algorithm that is known to perform not optimal yet "good enough".

Although I'm not 100% sure, I guess it relates with the Knapsack problem which is ( as we are all supposed to now haha.. ) NP-complete.

Got nothing better to offer right now, but good luck!

Hubbub

Answer 5

might this be an lp problem? http://en.wikipedia.org/wiki/Linear_programming

Enamelware

Answer 6

Unbounded Knapsack using Dynamic Programming is your answer.

Ridgeway