How to optimize shopping carts for minimal prices?

Answer 1

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.

Answer 2

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).

Answer 3

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