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?