Retail Discount Knapsack – Marginal Value Ranking Algorithm I
We often interpret retail discount best deal problem as a strict multi-dimensional integer knapsack problem. It is true for non-threshold discounts in general, but unfortunately, not for threshold discounts because of the way we apply them. (Click on the link to see more details.) In addition, it can run into performance problem in two cases: it generates too many basic discount applications to begin with or it takes too long for a knapsack algorithm to execute. We need to have an alternative algorithm that is fast, strive for the great deal, but does not guarantee the best deal.
Introduce marginal value ranking algorithm. Marginal value is an economics term: given what you have already, what is the value of having one more. For example, say you like apple. You have not had any today, what is the value of having the first apple. Then after you have your first apple, what is the value of having the second (one more)?
Back to retail discounts, one way to apply the discounts is to rank each of them by average marginal value over overlapped products. As an example, we have two discounts: D1 covers product A and B, and D2 covers product B only, so B is the overlapped product.
D1 average marginal value = (Value(D1 for A and B) – Value (D1 for A)) / Quantity(B)
D2 average marginal value = Value (D2 for B) / Quantity(B)
After the marginal value ranking, we would apply the discount with higher marginal value, and after that apply the discount with lower marginal value with leftover products.
Obviously, it is not perfect. There is room for fine-tuning. Until next time.
Related: Retail Discount Concurrency – Best Deal Knapsack Problem