% 
% Optimizing shopping basket in MiniZinc.
% 
% From 
% http://stackoverflow.com/questions/2822082/how-to-use-constraint-programming-for-optimizing-shopping-baskets
% """
% How to use constraint programming for optimizing shopping baskets?
% 
% 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?
% """
% 
% Note: This is not what was asked for, but since I'm so lazy I
% modelled it in MiniZinc instead.
%
% This MiniZinc model was created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc
%

%
% Later note: I added an extra shop which don't have item 1,
% coded as a very large price (999999999).
% Another way is maybe to set the price to 0 and require that
% the prices to use is > 0.
%

% data defined below
int: num_items;
int: num_shops;
array[1..num_shops] of int: delivery_costs;
% assumes cost 0 if above the limit
array[1..num_shops] of int: delivery_costs_limits;
array[1..num_items, 1..num_shops] of int: costs;

%
% decision variables
%
% x: where to shop which item
% (alternative representation: one array with the domain of 1..num_shops)
array[1..num_items,1..num_shops] of var 0..1: x;

% total price
var int: total; 

solve minimize total;
% solve satisfy;

constraint

   % we must buy all items (from some shop)
   forall(i in 1..num_items) (
       sum([x[i,j] | j in 1..num_shops]) = 1
   )
   /\ 
   total = sum(i in 1..num_items) (
       % costs of the products
       sum(j in 1..num_shops) (
          x[i,j]*costs[i,j]
       )
   ) + sum(j in 1..num_shops) (
       %  and delivery costs if total for a shop < limit
       let {
         var int: this_cost = sum([costs[i,j]*x[i,j] | i in 1..num_items])
       } in
       delivery_costs[j]*bool2int(this_cost > 0 /\ this_cost < delivery_costs_limits[j])
   )
;


%
% data
%
% num_items = 2;
% num_shops = 2;

num_items = 3;
num_shops = 3;

% delivery_costs = [10,5];
% delivery_costs_limits = [150,50];

delivery_costs = [10,5,3];
delivery_costs_limits = [150,50,100];



% if a shop don't have an item, give it a very large price
costs = array2d(1..num_items, 1..num_shops, [ 
         % 100, 111,
         %  90, 85
         100, 111, 9999999,
          90, 85, 2,
          10, 10, 10
         ]
        );


output [
  "total: " ++ show(total) ++ "\n" ++
  "x: " ++ show(x) ++ "\n" 

];