How to optimize shopping carts for minimal prices?

I have a list of items I want to buy. The items are offered by different shops and different prices. The shops have individual delivery costs. I'm looking for an optimal shopping strategy (and a java library supporting it) to purchase all of the items with a minimal total price.

Example:

• Item1 is offered at Shop1 for $100, at Shop2 for $111.
• Item2 is offered at Sho开发者_如何学Pythonp1 for $90, at Shop2 for $85.
• Delivery cost of Shop1: $10 if total order < $150; $0 otherwise
• Delivery cost of Shop2: $5 if total order < $50; $0 otherwise

• If I buy Item1 and Item2 at Shop1 the total cost is $100 + $90 +$0 = $190.
• If I buy Item1 and Item2 at Shop2 the total cost is $111 + $85 +$0 = $196.
• If I buy Item1 at Shop1 and Item2 at Shop2 the total cost is $100 + $10 + $85 + $0 = 195.

I get the minimal price if I order Item1 and Item2 at Shop1: $190

Question

I need some hints which algorithms may help me to solve optimization problems of this kind for number of items about 100 and number of shops about 20.

I already looked at apache-math and its optimization package, but I have no idea what algorithm to look for.

---

Here is a follow up question.

---

Of all the algorithms in that package, none operate in a discrete solution space (i.e. none express the constraint that you can't buy half an item in shop 1, and half an item in shop 2).

You might attempt to recursively walk the solution starting from a good first guess (e.g. the optimal solution disregarding shipping costs), and backtrack early as soon as your current solution can not get better than the best seen so far. This is O(S^I), but if the shops offer differing prices, it might not be quite as bad. It would yield the optimal solution, though.

You might try an iterative approach, where you start with some solution, look at neighbouring solutions (only one item from a different shop), take the best of those, and repeat that until the solution doesn't change anymore. This approach might get stuck in local optima though, so it is often randomized, either in starting location, or by proceeding with a less than best neighbour solution with some probability (c.f. simulated annealing).

Or if you really want to dig into the literature, http://en.wikipedia.org/wiki/Combinatorial_optimization is a good starting point.

---

While you could implement your solution based on the Apache Simplex solver, you'll have to build a lot of code on-top of it to get it to do what you want.

A quicker approach is to use a ready-made Constraint Satisfaction package for integer domains which supports optimization. There are a number of open source packages available each with slightly different features. One that caught my eye was Cream. This is implemented purely in Java, has a very neat API, is based on a number of algorithms (branch and bound, taboo, simulated annealing, etc). It has some nice features like searching with time-out, parallel local searches, etc.

There are some other packages which you might want to investigate, but which I don't know much about:

1. JCL
2. jOpt

---

Sounds a bit like the 0/1 knapsack problem to me.

Essentially, you can model the problem as a decision tree (where each level is the decision of where to buy the product from and branches out into the different suppliers). Then you can trace the optimal solution.

Might need some adaption for your situation (to take into account shipping, etc.) but a good place to start looking.

Some information courtesy of Wikipedia

EDIT

I should add that, in this case it isn't really a 0/1 problem (i.e. take it or leave it), instead it's a 0-n problem (i.e you have n choices of supplier, or you can leave it).

---

For the record, one can run integer programming with constraints, so use a 0/1 (i.e. a binary variable) to indicate if a given product is to be bought at a given store, with the constraint: sum binary variables over stores (for a fixed product) <=1