Cannot find Algorithm that can find best way of applying coupon codes for a list of products

user_13532367 0
Viewed 270

Defining the Inputs

So basically you have a list of product pi, and each product have a list of possible coupon codes list[i]. List[i] contains all j possible the coupons applicable to pi.

array of products : p[i] = { p1, p2, p3, p4 ....}

product object :

p[i] = {
   price,
   coupons: list[i]
   // it contains reference to all the coupons applicable to this product
}

list[1] = {c1, c2, c3, c5 ...}
list[2] = {c1, c2 ...}
list[3] = {c2, c4, c5 ...}
list[4] = {c3, c4, c5 ...}
... and so on upto list[i]

coupon object in product list :

list[i][j] = {
    discount: Number, 
    // the amount which will be deducted from ith product if list[i][j] product is applied 
    
    name: String
    // the name of the product this basically tells,
    // that to which coupon in the pool of coupons does this coupon refer to.
}

Pool of all Coupons = {c1, c2 ,c2 ,c4 ,c5 ,c6, c7....}
coupon object in pool :

c[j] = {
    minPriceToAvail: Number,
}

note:

  • we can only apply one coupon at a time.

  • we don't have to buy everything at once we can buy multiple times.

  • we won't be able to apply a coupon if the sum total of all the products we are going to buy which have this coupon applicable is less than minPriceToAvail.
    For eg.s three products p1,p2,p3 with prices 2000,1000,500 and the min price to avail the coupon is 2000.
    This coupon is applicable on only p2 and p3 so we can not apply it,
    cause the sum total of all the products that have this coupon is only 1500

Example

p[i] = `{ shirt, laptop, book, mouse }`
// now every product have price and coupons list.

shirt = {
  price: 400,
  coupons: [ SALE10, DISC20, WELCOME ]
}
// each coupon here will have a discount amount and reference to pool of object 
// which here for simplicity let be the same as the name of the object


shirt.coupons.SALE10 = { discount: 100, name: SALE10 }

// this means that when this coupon will be applied,
// the price of the shirt will be deducted by 100

shirt.coupons.DISC20 = { discount: 20, name: DISC20 }
shirt.coupons.WELCOME = { discount: 0, name: WELCOME }


// similarly for every product

laptop = {
    price: 40000,
    coupons: [
        { discount: 10000, name: DISC10 },
        { discount: 15000, name: ELECTRO },
    ],
}
book = {
    price: 1000,
    coupons: [
        { discount: 30, name: LUCKY },
        { discount: 50, name: DISC10 },
        { discount: 400, name: BOOKS },
    ],
}

mouse = {
    price: 2000,
    coupons: [
        { discount: 200, name: LUCKY },
        { discount: 1000, name: WELCOME },
    ],
}

allCoupons = {
    SALE10: { minPriceTotal: 300 },
    DISC20: { minPriceTotal: 1000 },
    DISC10: { minPriceTotal: 500 },
    WELCOME: { minPriceTotal: 2500 },
    BOOKS: { minPriceTotal: 2000 },
    LUCKY: { minPriceTotal: 500 },
    ELECTRO: { minPriceTotal: 5000 },
}

Objective

The objective is to simply get the best possible combination of buying these products so as to reduce the cost to a minimum.
Just need to know the algorithm to apply here . Search Pruning is one thing that is in my mind right now but I think won't be as efficient as required.
I can only find the naive recursive solution which will run in O( product of n(li) ), i.e. In Order of Product of number of coupons in each product.
Like in the example below the product will be 3*2*3*2 = 36

linear-programming dynamic-programming recursion algorithm
1 Answers

Here is a MILP-formulation

data:

D_p_d: price discount for product p and discount d
T_d: min total price for discount d
P_p: price of product p
M: large enough number

variables:

x_p_d: 1 if product p bought with discount d otherwise 0
z_d: 1 if discount d used otherwise 0

model:

min sum_p(P_p) - sum_p(sum_d(D_p_d*x_p_d))
subject to

    1. sum_d(x_p_d) <= 1, for all p (use max one discount per product)
    2. M*z_d >= sum_p(x_p_d), for all d (connect x and z)
    3. z_d <= sum_p(x_p_d), for all d (connect x and z)
    4. M(1-z_d) >= T_d - sum_p(P_p*x_p_d), for all d (discount can only be used if total price is at least minPriceTotal)

This can be implemented e.g. with PuLP, here is a MiniZinc implementation (where the M values have been tightened):

int: nProducts = 4;
int: nDiscounts = 7;

set of int: PRODUCT = 1..nProducts;
set of int: DISCOUNT = 1..nDiscounts;
                     
array[DISCOUNT] of int: minPriceTotal = [300, 1000, 500, 2500, 2000, 500, 5000];

array[PRODUCT, DISCOUNT] of int: discount = [|
    100, 20, 0, 0, 0, 0, 0|
    0, 0, 10000, 0, 0, 0, 15000|
    0, 0, 50, 0, 400, 30, 0|
    0, 0, 0, 1000, 0, 200, 0|];
    
array[PRODUCT] of int: price = [400, 40000, 1000, 2000];

array[PRODUCT, DISCOUNT] of var 0..1: x;
array[DISCOUNT] of var 0..1: z;

% use max one discount per product
constraint forall(p in PRODUCT)
    (sum(d in DISCOUNT)(x[p, d]) <= 1);

% connect x and z
constraint forall(d in DISCOUNT)
    (nProducts*z[d] >= sum(p in PRODUCT)(x[p, d]) /\ 
     z[d] <= sum(p in PRODUCT)(x[p, d]));

% discount can only be used if total price is at least minPriceTotal
constraint forall(d in DISCOUNT)
    (max(minPriceTotal)*(1 - z[d]) >= minPriceTotal[d] - sum(p in PRODUCT)(price[p]*x[p, d]));
            
var int: obj = sum(price) - 
    sum(p in PRODUCT, d in DISCOUNT)(discount[p,d]*x[p,d]);

solve
minimize obj;

output ["obj=\(obj)\n"] ++
["z=\n"] ++ [show(z)] ++
["\nx=\n"] ++ [show2d(x)];

Running gives:

obj=27300
z=
[1, 0, 0, 1, 0, 0, 1]
x=
[| 1, 0, 0, 0, 0, 0, 0 |
   0, 0, 0, 0, 0, 0, 1 |
   0, 0, 0, 1, 0, 0, 0 |
   0, 0, 0, 1, 0, 0, 0 |]

Interpretation:

  • buy first product using first discount (SALE10). Discount = 100
  • buy second product using seventh discount (ELECTRO). Discount = 15000
  • buy third&fourth product using fourth discount (WELCOME). Discount = 0 + 1000
user_108428820
Related