Minizinc piecewise linear function

I have a cost minimization problem.In the problem we have 3 suppliers. They are S1,S2 & S3, where cost is calculated as price x Qty purchased.

Price value for 3 suppliers as follows.

price=[10,15,20]

If I have a decision variable as array[1..3] of var int:purchase where I am going to get the answers from optimization problem from which supplier how many units I need to purchase.

Sample code as follows.

enum suppliers={s1,s2,s3};
int: len_sup=length(suppliers);
set of int:range_sup=1..len_sup;

array[range_sup] of int:price=[10,15,20];
int:demand=40;

array[range_sup] of int:moq=[5,0,5];
array[range_sup] of int:maxoq=[8,20,30];

array[range_sup] of var 0..100:purchase;

constraint sum(i in range_sup)(
purchase[i])=demand
;

constraint forall(i in range_sup)(
purchase[i]>=moq[i] \/ purchase[i]=0
);

constraint forall(i in range_sup)(
purchase[i] <= maxoq[i]
);

var int:cost;

constraint sum(i in range_sup)(
purchase[i]*price[i])=cost;

solve minimize cost;

Now I have a new requirement to embed price discounts for this.This price discount will definitely vary from the qty we purchase.

for this example imagine it is known that from any supplier if we purchase Qty of 1 to 5 then we would get 5% discount (price would decrease from 5%) on the price. If we purchase 6 to 10 we get 10% price discount. If we purchase more than 11 we get 15% price discount.

How do you incorporate this thing to model.Is this using by piecewise linear functions (because it seems like problem becoming non linear)? Can someone show how could this using piecewise linear function?

Solution

Perhaps this don't really answer your question, but for some solvers (e.g. Gecode, JaCoP, and OptiMathSAT) you can use a lookup table for this.

You can add a simple discount table:

array[1..3,1..3] of float: discount = array2d(1..3,1..3,
[
 1,5,0.05,  % between 1 and 5: 5% discount
 6,10,0.10, % between 6 and 10: 10% discount
 11,1000,0.15, % 11.. 5: 15% discount
]);

and change the cost constraint to

constraint
cost >= 0 /\
cost =
sum(i in range_sup) (
   purchase[i]*price[i]
    % lookup the discount 
    - purchase[i]*price[i]*sum(r in 1..3) (
          discount[r,3]*(purchase[i] >=  discount[r,1] /\
          purchase[i] <= discount[r,2]
      )
 ;

The optimal solution will then be

purchase = array1d(1..3, [8, 20, 12]);
cost = 531;

As mentioned earlier, this works only for solvers that support var float variables and also the non linear float_times.

Update: suresh_chinthy asked about piecewise_linear. Here's an example how to use it. Note that it will work with Gecode, JaCoP, OptiMathSAT, but not with linear solvers such as CBC since piecewise_linear returns a var float which is multiplied with the decision variable purchase[i] (which is var inte) and this is not allowed in CBC.

Change the discount table from the code above, with these two arrays. Here we assume that it's possible to buy between 0 and 40 items.

% the amount of purchase
array[0..40] of float: discount_base = array1d(0..40,[i | i in 0..40]);
% the discounts for each purchase
array[0..40] of float: discount =
   array1d(0..40,
           [0.0, % 0
            0.05, 0.05, 0.05, 0.05, 0.05, % 1-5
            0.10,0.10,0.10,0.10,0.10, % 6-10,
            0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15, % 11-20
            0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15, % 21-30
            0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15, % 31-40                        
            ]);

And the cost constraint is changed to

constraints
  cost > 0 /\
  cost = 
       sum(i in range_sup) (
       purchase[i]*price[i] - purchase[i]*price[i]* piecewise_linear(1.0*purchase[i], discount_base, discount)
  );

The result is the same as above:

purchase = array1d(1..3, [8, 20, 12]);
cost = 531;