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?

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.