A very simple discrete algorithm for smoothing out impulses to a target constant value

Demand smoothing

Let’s assume you use a lot of toilet paper at your home. Some number of rolls per week(integer rolls). If you buy new packages of toilet paper once a month, let’s figure out a simple algorithm to keep your bathroom well-stocked.

Roll up weekly data

Each week, we have our usage, but since we’re only buying once every month we need to consider the sum over the weeks inside. Consider M-S weeks, then the months have the following number of Sundays:

[4,4,4,5,4,4,5,4,5,4,4,5]

We’ll return to this later.

Available rolls

We dont want to run out, period. As not-a-risk taker, and someone who occasionally throws parties, I want at least twice as much TP around as I normally need. Let’s then say whatever my biggest usage per week is, times two, will be my target t.

Minimizing Error

Because we have a target for available rolls, our goal throughout the month, is to have our order keep us as close to that value as possible.

For i, \(1 ≤ i ≤ 5\) the numbered weeks in the month, and u_i the corresponding TP usages. Also assume that before you buy some more TP, you have o the “on shelf” TP from the month before. We’ll be calculating our TP purchase x

We wish to minimize

\[\mathop{\arg\,\min}\limits_x\left(\sum_i\left(\mid x+o-\sum^i_j u_j -t \mid\right)\right)\]

This feels like something that should be somewhat easy to minimize, and to a certain extent it is. It relies on a little lemma though:

Little Lemma

For a set of numbers S, and a value Y

\[\mathop{\arg\,\min}\limits_{s \in S}\left(\sum_i\left(\mid S - Y \mid\right)\right) = median\left(S\right)\]

So let \(Y= x+o-t\), and consider instead, the partial sums \(U_i = \sum^i_j u_j\), then

\[\mathop{\arg\,\min}\limits_x\left(\sum_i\left(\mid x+o-\sum^i_j u_j -t \mid\right)\right) = \mathop{\arg\,\min}\limits_{U_i}\left(\sum_i\left(\mid U_i - Y \mid\right)\right) = median\left(U_i\right)\]

Ap-PLY-ing our algorithm

To compute a year’s worth of TP purchases, we need now apply the previous. Let’s start by assuming our TP consumption is exactly last years(broken into months):

weekly_usage = [
  [4,3,2,4,],
  [3,3,2,4,],
  [3,5,3,2,],
  [4,5,3,3,2,],
  [4,3,3,2,],
  [6,4,3,3,],
  [2,7,4,3,3,],
  [4,2,4,3,],
  [3,6,2,4,3,],
  [3,2,11,2,],
  [4,3,7,3,],
  [2,4,3,3,5,],
]

Now we need to send each of these little lists into the median calculator:

partial_sum = lambda a, b: a + [a[-1] + b]

def take_median_or_upper_bound_of_partial_sums(list_of_ints):
  return reduce(
    partial_sum,
    list_of_ints[1:],
    list_of_ints[0:1],
  )[len(list_of_ints)/2 if len(list_of_ints) > 2 else -1]

And then we can just run through our weekly usage in blocks of months:

monthly_purchases, start_of_month_availability = [], incoming_availability
for month in weekly_usage:
  necessary = max(
    take_median_or_upper_bound_of_partial_sums(month) -
    start_of_month_availability +
    (target or 0),
    0
  )
  monthly_purchases.append(necessary)
  start_of_month_availability = necessary + start_of_month_availability - sum(month)

A gotcha

If you dont start exactly when you’re buying, every week that passes before you buy needs to be subtracted from the start_of_month_availability to start with:

start_of_month_availability = incoming_availability - used_before_first_order

Example

As an example, with the data above, you can compute the purchase amounts. In this case let’s assume the incoming_availability is 12 and our target is twice the biggest week’s usage: 22, it looks like this:

purchase: 19
current available: 31
current available: 27
current available: 24
current available: 22
purchase: 12
current available: 30
current available: 27
current available: 24
current available: 22
purchase: 15
current available: 33
current available: 30
current available: 25
current available: 22
purchase: 14
current available: 34
current available: 30
current available: 25
current available: 22
current available: 19
purchase: 15
current available: 32
current available: 28
current available: 25
current available: 22
purchase: 15
current available: 35
current available: 29
current available: 25
current available: 22
purchase: 16
current available: 35
current available: 33
current available: 26
current available: 22
current available: 19
purchase: 16
current available: 32
current available: 28
current available: 26
current available: 22
purchase: 14
current available: 33
current available: 30
current available: 24
current available: 22
current available: 18
purchase: 23
current available: 38
current available: 35
current available: 33
current available: 22
purchase: 16
current available: 36
current available: 32
current available: 29
current available: 22
purchase: 12
current available: 31
current available: 29
current available: 25
current available: 22
current available: 19