Retail Discount Concurrency – Best Deal Knapsack Problem

  • Article

Update - the blog post has been moved to Dynamics 365 Community.

What happens when a product is covered by multiple discounts? It’s often referred as discount concurrency problem. Today, we’ll cover the case where none of them can be compounded on top of each other, in other words, you can apply only one discount on one product. The most common goal is to get the best deal for the customer.

Let’s elaborate with an example.

  • Two products, keyboard costing $20, and mouse $10.
  • A simple discount of 40% for both.
  • Buy one get (least expensive) one free for both.

Best deals with various combination of products in a transaction.

Transaction setup Best deal Alternative Comment
2 keyboards B1G1 free for $20 Simple discount for $20*2*40% = $16
2 mice B1G1 free for $10 Simple discount for $10*2*40% = $8
1 keyboard, 1 mouse Simple discount for $20*40%+$10*40%=$12 B1G1 free for $10
2 keyboard, 1  mouse B1G1 free for 2 keyboards: $20, and simple discount for 1 mouse $4. Total $24 Simple discount for all. $20*2*40%+$10*40%=$20 We have more alternatives, e.g. B1G1 free for 1 keyboard and 1 mouse: $10, and simple discount for 1 keyboard: $8. Total $18

When the number of products is small and product quantities are low, we humans can figure it out easily. As the number of products, and/or product quantities increase, it’s not a trivial task to figure out the best combination that would give you the best deal.

In essence, it’s a multi-dimensional integer knapsack problem. Back to the same discount setup, but with more products. We have 5 basic discount applications:

Id Basic discount application
S1 Simple discount for 1 keyboard of $8
S2 Simple discount for 1 mouse of $4
MM1 B1G1 for 2 keyboards of $20
MM2 B1G1 for 2 mouse of $10
MM12 B1G1 for 1 keyboard and 1 mouse of $10

 

Any deal would be constructed by a combination of zero or more of any of the 5 basic discount applications. In addition, we cannot break down the 5 basic discount applications further.

  1. It’s a knapsack problem . To figure out the best deal, we need to try various combinations of zero or more of any of the 5 basic discount applications bounded by product quantities in the transaction, compare them and select the combination that gives the best deal.
  2. It’s a multi-dimensional knapsack problem. Each product would be one dimension.
  3. It’s an integer knapsack problem. We cannot break down keyboard in half. For scale products, say 3.5 pounds’ apple, if we consider it as a whole for discount, then conceptually speaking, it’s still an integer knapsack problem. In other words, we don’t break it down into, say, 10% off 1.7 pounds and 15% off 1.8 pounds.
  4. It can be an unbounded or bounded knapsack problem. In this example, it’s an unbounded knapsack problem. By bounded, say if in this example, you can get the simple discount up to 2 per product, then it’s a bounded knapsack problem. Please note that bounded here refers to the number of times you can apply a discount for any transaction setup, it’s different from being bounded by the product quantities in one transaction.

We will discuss the solutions in another post.