Retail Discount Concurrency – Best Deal Knapsack Problem

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.

Comments

• Anonymous
  December 03, 2018
  Hi, ZhiyiI'm working on something similar to this problem. By searching online I realized it is a unbounded multi-dimensional knapsack problem. What troubles me is the number of products are too many and so are the basic discount applications. Suppose there are 200 products and between any two products there is a basic discount application. So we have 200*199/2 = 19900 different basic discount applications. I've tried some packages in Python to solve the problem but it failed because out of memory. Do you have any suggestion to solve the problem. Thanks a lot.Tian
  • Anonymous
    December 03, 2018
    You hit one of the issues: too many discount applications. Before we get to details, we have to realize that for any algorithm, it's not hard to come with a setup that makes it really slow. In other words, in the context of discount, it's not practical to get the best deal all the time. To alleviate the problem, we need to aim a bit lower, and we need backup plan(s). I've covered it a bit in this blog.Back to your question. In some cases, what you mentioned can be optimized. For example, 1. If price for many products are the same, then you group same-price products as one for discount calculation. (I talked a bit about discountable item group in my blog.)2. If this is the only discount - no overlap with other discounts over the same set of products - in many cases, you can sort out best deal without going through knapsack problem.If you're working on a generic problem, it's hard, but if you're practical and willing to bend a bit, you can come up with practical solutions.If you have more details, I'd love to hear them.
    • Anonymous
      December 06, 2018
      Thanks for your quick reply. Actually I have solved the problem by using more powerful computer. However, your advice and blog still help. When my model goes to be more complicated, I may still need your advice. Thanks again.