How to use constraint programming for optimizing shopping baskets?
- by tangens
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?
