Retail Discount Design – Mix and Match with Amount Qualification

Artikel
05/24/2017

We covered mix and match with fixed quantity in the past. What about minimal amount threshold?

Setup

One qualifying group with amount threshold
One application group with fixed quantity

Example: buy shirts worth $100+, get a free tie.

Preliminary analysis

In general, it is not suited for the dynamic programming algorithm for discount best deal problem, in that the number of possible basic discount application can mushroom exponentially as number of qualifying items increases. For example, amount threshold is $100, and you have items from $9, $10, all the way to $25, how many possible basic discount application can you have?

The recommendation is not to get it into discount best deal algorithm. Instead, finish it post-best-deal-algorithm, as we did for mix and match least expensive favor retail discount.

For qualifying, a common goal is to maximize number of qualifying groups for a given transaction. For example, 4 shirts: $40 $50 $60 $70. If you make $60 and $70 a group, then the other two will not qualify. One maximizing grouping would be {$40, $70} and {$50, $60}

How to apply the mix and match when it is (or as if it were) the only discount for the checkout cart?

For now, we assume qualifying group and application group do not overlap.

As we discussed earlier, the problem we have to solve is to maximize the number of qualifying groups, given the items in the checkout cart.

If the price of an item >= the minimal amount threshold, then it itself can make a qualifying group. We can single them out and work on the rest. From now on, we will assume all item prices < minimal amount threshold.
First, we can get maximum number of discount applications possible, by dividing total price by the minimal amount threshold. During the evaluation, if we reach it, then we can quit.
In addition, we may adjust maximum number of discount applications possible by checking number of application groups

Now, it becomes a generic problem: given a list of decimal numbers, a threshold number and a possible maximum number of groups, find an arrangement of groups,

Satisfying: for each group, sum(number) > = threshold number
Maximizing the number of groups, up to the possible maximum number of groups.

This is not a trivial problem.

If you want a fast, saying linear complexity solution: Form groups one by one, by getting one item at a time, if total price reaches minimal threshold, then finish the group and start a new group.

Obviously, this does not always give you the maximum number of discount applications, but we can apply some optimization if it does not. As an example â€“ you can come up with your own as well - we can check if we can swap items between high priced items in groups and low priced in leftover items, and we may be able to form a new group. It is relatively fast. While it does not guarantee the maximum, it often works well.

To solve the problem fully, we can apply dynamic programming. In short, if we can solve the problems for all first i items, where i between 1 and n, we can solve the problem for n+1. It is similar to this text justification problem. Now, this may not finish in reasonable amount of time, so we have to interrupt it if necessary, and resort to a backup algorithm, for example, the one we discussed earlier.

Qualifying group and application group overlap

We have to decide whether to put the item in the qualifying group or the application group. In general, the goal is to maximize total number of discount applications.

Multiple mix and match discounts with amount threshold

First, we should avoid setting up conflicting mix and match discounts with amount threshold. If we cannot guarantee non-conflict, we need to figure out a way to rank them, so we can apply them in a sequential order. One way to rank overlapped discounts is to compare marginal values for discounts over the overlapped items.

Freigeben über