I work for Microsoft Dynamics Retail team. From now on, I will talk more about Dynamics Retail Discount Engine. The building blocks for discount knapsack problem are the basic discount applications, and I will share how we model discount application in Dynamics Retail Discount Engine.

We will first discuss discount application related concepts* in the context of knapsack algorithm.*

– discount application*DiscountApplication *

It covers how it is composed, like product quantities, for example, it takes one keyboard and one mouse. It has details for discount calculation and allocation to its products.

– applied discount application*AppliedDiscountApplication *

If everything is non-compoundable, then we may get away without it. Given compounding makes the value of a discount application dependent on what has been applied before, we need applied discount application to capture the conditional value of a discount application.

– discount application multiple*DiscountApplicationMultiple *

Recall that we can turn an unbounded/bounded integer knapsack problem into zero-one integer knapsack problem by applying a binary transformation. In short, a discount application (DA) becomes 1xDA, 2xDA, 4xDA, 8xDA, etc.

– composite discount application*CompositeDiscountApplication *

In many cases, we can turn a discount knapsack problem with compounded discounts into one without. The key ingredient is the composite discount application that consists of multiple discount applications, of which at most one is for complex discount (or non-simple discount).

– base discount application*BaseDiscountApplication *

For a knapsack algorithm to avoid dealing with both discount applications and composite discount applications, we abstract out base discount application from them.

** Not everything in discount engine is knapsack**. For example, when a discount has no competition, we may apply it in a simple way. To leverage what we have in knapsack algorithm, we

**,**

*reuse discount application***and**

*applied discount application***in non-knapsack scenarios. In this case, the discount application multiple is not restricted to binary form. In fact, the multiplier in the discount application multiple can be any positive integer.**

*discount application multiple*** Related**: Retail Discount Concurrency – Best Deal Knapsack Problem

** Related**: Dynamic Programming for Retail Discount Knapsack Problem

** Related**: Discount Best Deal Algorithm – Mixing in Compounded Discounts I