31

I'm in need of expert advice on a tricky matter.

The scenario is:

  • e-commerce web-site
  • lots of products
  • lots of discounts mixed on these products

A product is identified by a unique ProductID and has a sales price. Very classic scenario. The product can also be in one or more discounts.

A discount can be of different types. One example of a discount is:

  • Buy two or more within a set of products and get X percent off each product

A line item can only get one discount thus once a line item has been discounted it is not available for other discounts.

Test Case Data:

  • Product-1: $10
  • Product-2: $10
  • Product-3: $50
  • Product-4: $100

Discount-A: Buy two or more and get 20 % off the any of the following products

  • Product-1
  • Product-2
  • Product-3
  • Product-4

Discount-B: Buy product and get 50 % off the following product

  • Product-3

Test Scenario 1:

Basket: containing line items with:

  • Product-1
  • Product-3
  • Product-4

Calculation #1:

  • Discount-A: Product-1, Product-3, Product-4 = $2 + $10 + $20 = $32
    • = $32 total saving

Calculation #2:

  • Discount-A: Product-2, Product-4 = $2 + $20 = $22
  • Discount-B: Product-3 = $25
    • = $22 + $25 = $47 total saving

Which means that a combination of Discount-A and Discount-B will give the best possible discount for the customer.

Test Scenario 2:

Basket: containing line items with:

  • Product-3
  • Product-4

Calculation #1:

  • Discount-A: Product-3, Product-4 = $10 + $20 = $30
    • = $30 total saving

Calculation #2:

  • Discount-B: Product-3 = $25
    • = $25 total saving

Which means that applying Discount-A will give the best possible discount for the customer.

In order to calculate the best discount for a given basket, literally all combinations of products and available discounts on these products must be evaluated.

Normally there is 30-40 line items in a basket each with 0-3 discounts each.

Basically I'm stuck with finding an efficient way to do this calculation.

Right now the algorithm I have for applying the discounts is something like:

  • Clear discounts on the Basket
  • Get all unique ProductID's for LineItems in the Basket
  • Get all discounts available for these ProductID's
  • For-Each Discount (unordered)
    • Apply the Discount if it is satisfied by non-discount flagged line items
      • Flag line items in discount as discounted

But this is not at all sufficient as it does not try out different combinations of line items / discounts.

I've been searching around for standardized algorithms that can solve problems like this, but without any luck so far.

Hope to hear from you :)

Brian Holmgård Kristensen
  • 321
  • 3
  • 6
  • 1
    Is it necessary for the solution to be optimal? Seems to me that this is NP hard and lacks optimal substructure so it can't be solved dynamically. Of course, it is simple to brute force, but 30-40 items with a few discounts each doesn't sound good. – svinja May 17 '13 at 11:55
  • 1
    It is NP-hard by a reduction from set cover unless the discounts are less complicated than it currently seems. "A discount can be of different types" Could you tell us all of the different types of discounts? – David Eisenstat May 17 '13 at 12:41

1 Answers1

13

Assuming that:

  1. You can compute all available discounts based on your basket
  2. Each product can only have a single discount applied to it
  3. Each discount can only be used once

Then the problem becomes one that is called an assignment problem and can be optimally solved in O(n^3) using the Hungarian algorithm.

You will need to compute a matrix M[a,b] containing the money saved if using discount a on product b. (If a discount does not apply, then set the money saved to 0.)

The Hungarian algorithm will compute the way of assigning discounts to products that saves the most money.

If you don't have the same number of discounts and products, then add dummy discounts (with zero savings) or dummy products (again with zero savings) until the number of discounts matches the number of products.

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
  • Hi Peter, this looks really promising! Thanks a lot for your input. I'll leave this question open for a few days to see if more input is received. I won't forget to mark it as answered. Thanks. – Brian Holmgård Kristensen May 17 '13 at 12:50
  • @BrianHolmgårdKristensen For your basket of Products 3 and 4, this gives a discount of $45 – $25 on Product 3 via B, and $20 on Product 4 via A, using Product 3 to trigger but not receive the second discount. – David Eisenstat May 17 '13 at 13:07
  • @David - Thanks, you are quite right - I'd read the restriction as meaning to apply the discount only to non-discounted products, but I'd missed that additionally the discount can only be produced from non-discounted products. – Peter de Rivaz May 17 '13 at 18:08
  • How does the last restriction influence the algorithm? If you can only produce discounts based on products that have not already been included in another discount you can't use your answer directly. – Marius Sep 25 '13 at 08:44
  • @PeterdeRivaz Are you able to solve this problem? I stuck at the same point. – Hasmukh Rathod Dec 24 '18 at 08:55