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 Shop1 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
What I tried so far
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:
- each price "p xy" is defined in the domain (0, c) where c is the price of the item in this shop
- only one price in a line should be non zero
- if one or more items are bought from one shop and the sum of the prices is lower than limit, then add shipping cost to the total cost
- shop total cost is the sum of the prices of all items in a shop
- total cost is the sum of all shop totals
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.
Question
How should I express my constraints to make this problem solvable for a constraint programming solver?