How to proportionally distribute discount on order lines?

Question

I have an order with number of lines and discount that needs to be distributed between those lines proportionally to line costs.

I'm not a mathematician, so I'd introduce this notation to explain the case. An order has N lines, price for item is Pi, item quantity is Qi, total line cost is Ti where Ti = Qi * Pi. Total order price is T = sum(Ti). Algorithm need to distribute discount D, outcome is list of Di - distributed discounts for each order line. Result must satisfy following conditions:

D = sum(Di): sum of line discounts must be equal to original discount
Di%Qi = 0: discount must be divisible to quantity without remainer
Di <= Ti: discount must not exceed total line cost
- Di/D ~ Ti/T: discount is distributed as proportionally as possible

Input data satisfies following predicates:

D <= T, discount does not exceed total order cost
D, Di and Qi are integer values, Pi is decimal value
There are variations of input data that can't satisfy required conditions. For example, 3 lines, each has 3 items with price 10, input discount is 10 (N=3; Qi=3; Pi=10; D=10). There is no way to distribute it divisible to line counts. For this cases algorithm should return error with amount of discount that can not be distributed (for my example it's 1)

Now our implementation of algorithm looks like this (simplified version on F#)

type Line = {
  LineId: string
  Price: decimal
  Quantity: int
  TotalPrice: decimal
  Discount: decimal
}

module Line =
  let minimumDiscount line =
    line.Quantity
    |> decimal
    |> Some
    |> Option.filter (fun discount -> discount <= line.TotalPrice - line.Discount)

  let discountedPerItemPrice line = line.Price - line.Discount / (decimal line.Quantity)

let spread discount (lines: Line list) =
  let orderPrice = lines |> List.sumBy (fun l -> l.TotalPrice)
  let preDiscountedLines = lines |> List.map (fun line ->
    let rawDiscount = line.TotalPrice / orderPrice * discount
    let preDiscount = rawDiscount - rawDiscount % (decimal line.Quantity)
    {line with Discount = preDiscount})

  let residue = discount - List.sumBy (fun line -> line.Discount) preDiscountedLines

  let rec spreadResidue originalResidue discountedLines remainResidue remainLines =
    match remainLines with
    | [] when remainResidue = 0m -> discountedLines |> List.rev |> Ok
    | [] when remainResidue = originalResidue -> sprintf "%f left to spread" remainResidue |> Error
    | [] -> discountedLines |> List.rev |> spreadResidue remainResidue [] remainResidue
    | head :: tail ->
      let minimumDiscountForLine = Line.minimumDiscount head
      let lineDiscount = minimumDiscountForLine
                           |> Option.filter (fun discount -> discount <= remainResidue)
                           |> Option.defaultValue 0m
      let discountedLine = {head with Discount = head.Discount + lineDiscount}
      let discountedLines = discountedLine :: discountedLines
      let remainResidue = remainResidue - lineDiscount
      spreadResidue originalResidue discountedLines remainResidue tail

  spreadResidue residue [] residue preDiscountedLines

This algorithm adapts some of the solutions found here and works for most of the cases. Hovewer, it fails on cases like:

P1=14.0; Q1=2;
P2=11.0; Q2=3;
D=52

There is at least one possible distribution: D1=22; D2=30, but current algorithm fails to discover it. So what's better algorithm of spreading or better algorithm of spreading residue in particular?

score 0 · Answer 1 · answered Feb 15 '19 at 13:29

Let's interpret Di/D ~ Ti/T as Di ∈ {Qi*floor(D*Pi/T), Qi*ceiling(D*Pi/T)}. Then we can solve this problem as a subset sum, viz., for every i such that D*Ti/T/Qi is not an integer and for which Qi*ceiling(D*Pi/T) ≤ Pi, we have an item of weight Q_i, and the target sum is D - sum_i Q_i*floor(D*Pi/T). Subset sum is NP-hard, but only weakly so, and unless you have enormous quantities, solving it should be no problem using the conventional dynamic program. If the problem is infeasible, you can use the final tables from the dynamic program to figure out what the best remainder is.

As an extension, you may want to favor solutions where, although D*Ti/T is not an integer, Di is closer to that ratio than the alternative. You can define item profits like |floor(D*Ti/T/Qi) - D*Ti/T|^2 - |ceiling(D*Ti/T/Qi) - D*Ti/T|^2 that favor items where the optimal discount is closer to the ceiling than the floor. Then you're solving a knapsack problem (well, sort of, since the "profits" can be negative) instead of subset sum, but the DP doesn't change much.

How to proportionally distribute discount on order lines?

1 Answers1