Let’s design the mix and match. For the first installment, we will talk about fixed quantity setup and focus on best deal for the customer.

*Setup*

. In some cases, you choose a fixed number of products (quantity) from one set of products. For example, buy two shoes, get one (least expensive) shoe free (B2G1 free), or B1G1 50% off. In other cases, you need to choose from multiple sets of groups. For example, buy one Xbox console, get two free games. In short, we define one or more line groups, each requiring a fixed number of products. In addition, we specify product set for each line group.*Line group*. The most common ones are bundle deal price, total amount off, percentage off and least expensive, where least expensive has 3 flavors, as in the following: buy one get second (least expensive) one for 1c, buy two get third one for 50% off, buy one get second one $5 off. For least expensive, the number of least expensive products can be more than one, for example, it is two in B3G2.*Discount method*

*How to apply the mix and match when it is the only discount for the checkout cart?*

In many cases, to get the best deal, we can order products by price for each line group, and apply one after another from highest priced product to the lowest in each line group.

Unfortunately, it does not work in some cases.

. For example, we want to promote keyboards and mice, and a bit more on keyboards, so we set up mix and match like this: buy one keyboard and another keyboard or mouse, get the least expensive one 50% off. Now what is the best deal (mix and match combinations) if you buy 5 keyboards and 3 mice. I will leave it as exercise to figure out a scenario where best deal would leave out some products. Hint: the best deal depends on the price difference of keyboard and mouse.*Line groups with overlapped products*. For example, $10 off if you buy any two keyboards. We buy two fancy keyboards, each of $20, and two cheap ones, each of $4. I’ll leave it to reader to figure out why working from highest price to lowest won’t get you the best deal.*Total amount off with some products having too low a price to get full benefit of the discount*

In case when it is not trivial to figure out the best deal, we could turn it into a discount knapsack problem, which is similar to the case below with competing discounts.

** Mix and match competes with other discounts**.

This is essentially a knapsack problem: figure out the best combinations from a pool of choices. The first step for discount knapsack problem is to ** figure out basic discount applications** for all applicable discounts, including the very mix and match. The algorithm for mix and match with fixed quantity setup is straightforward combinatorial algorithm: we just exhaust all possible combinations. Now we could get a huge list, which means we need a backup plan. We will talk about backup plan shortly afterwards.

At the beginning of the knapsack problem, we will ** pre-calculate discount values for all basic discount application**.

In most cases, an effective discount knapsack algorithm will finish it in time.

** What happens if it cannot**? We need a backup plan where we strive for best deal in a short time, but do not guarantee it. A common case is to rank discounts (not discount applications) in some way, and then apply one discount after another.

In other words, we ** estimate some value for each discount** and rank them by the value. Then we

**by the rank.**

*apply each discount fast**Compounding*

For any discount, compounding means you’ll need to ** take into account already applied compoundable discounts to figure out the discount value for a mix and match discount application**.

Compounding makes things messy, sometimes, a lot. The good news, in many cases, we can turn a discount knapsack problem with compounded discounts into a non-compounding discount knapsack problem.

If you were wondering earlier why we pre-calculate the value for a discount application - why not just calculate - compounding make the value dependent on other applied discount applications. To accommodate it, in general we calculate the value when we apply the discount application.

**Optimizations**

We actually already talked about it earlier where the mix and match discount has no other competitions. Given each retailer’s common discount setup, we can have more optimization. As always, we’ll need to weigh benefit against cost.

**Partial quantity**

By default, we do not deal with scale products with this kind of mix and match setup. Any interest case is cheese, which I may blog about it in the future.

** Related**: Retail Discount Concurrency – Best Deal Knapsack Problem