Discount Best Deal Algorithm Performance

As we discussed before, retail discount best deal problem is a multi-dimensional integer knapsack problem. One algorithm to solve the problem is dynamic programming, with pseudo-polynomial complexity.

Let's look at the performance today.

Number of basic (atomic) discount applications can be huge.

Before we get into any knapsack algorithm, the first step is to generate a list of basic (atomic) discount applications from all applicable discounts for the products in the transaction. In most retail transactions, the number is small, but it can get huge, even with a plain discount definition.

For example, mix and match of 6, you get 20% off. In the following table – simple combination arithmetic - we assume quantity for each product is one. The number would be even larger if the quantity is more than one.

Algorithm can take a long time.

Take dynamic programming as an example. Assume that number of basic discount applications is n, and product quantities in the transaction is q₁, q₃,…,q_n, the complexity is the product of them all: n_*(q₁+1)_* (q₂+1)_*…_*(q_n+1). Now in reality the matrix is mostly sparse, but it can still be a huge number.

Common case optimization.

Pragmatically, we have to resort to special optimizations for some common cases.

Take the mix and match we mentioned earlier: 20% for 6. Assume there are no competing discounts for the covered products. To get the best deal, we can just order products by price, and apply the mix and match discounts from the highest-priced products first, until no more.

Let’s make it a bit more interesting, same mix and match: 20% for 6, and we have some competing simple discounts. The following can guarantee best deal.

1. For each product of quantity 1, calculated relative discount: discount value for mix and match minus discount value for simple discount, or D(m&m) – D(s).
2. Order products by relative discount with descending values.
3. From products of the highest relative discount, group by 6, if total relative discount of the 6 products is greater than zero, apply the mix and match, and keep iterating, or else stop.
4. Apply the simple discounts for the rest.

Reduce the size of the problem.

In many cases, we can reduce the size of the problem.

For example, we have two discounts, with mix and match covering product 1, 2 and 3, and simple discount covering all products. In transaction, we have product 1, 2, 3, 4, 5 and 6.

Given product 4, 5 and 6 are covered by simple discounts only, we can just apply them, and remaining (reduced) problem is competing discounts on product 1, 2 and 3 only.

Note: if we switch discount product coverage, say, mix and match covering all, while simple discount only 1, 2 and 3, we cannot reduce the problem.

Backup plan

We can optimize for some common cases, but we cannot for all. We need a backup plan for extreme cases.

That would be another post.

Related: Retail Discount Concurrency – Best Deal Knapsack Problem

Related: Dynamic Programming for Retail Discount Knapsack Problem