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.
I get the minimal price if I order Item1 and Item2 at Shop1: $190
I asked another question before that led me to the field of constraint programming. I had a look at cream and choco, but I did not figure out how to create a model to solve my problem.
| shop1 | shop2 | shop3 | ...
-----------------------------------------
item1 | p11 | p12 | p13 |
item2 | p21 | p22 | p23 |
. | | | |
. | | | |
-----------------------------------------
shipping | s1 | s2 | s3 |
limit | l1 | l2 | l3 |
-----------------------------------------
total | t1 | t2 | t3 |
-----------------------------------------
My idea was to define these constraints:
The objective is "total cost". I want to minimize this.
In cream I wasn't able to express the "if then" constraint for conditional shipping costs.
In choco these constraints exist, but even for 5 items and 10 shops the program was running for 10 minutes without finding a solution.
How should I express my constraints to make this problem solvable for a constraint programming solver?
I have implemented this problem in MiniZinc (a high level constraint programming language): shopping_basket.mzn. It is quite forward and maybe could be used as a model for your Java model.
For the Choco model, have you tried different search strategies? A different strategy may be faster.
By the way, one other Java constraint programming solver you may want to check out is JaCoP.