qbook sandbox

Convolution power










Home » Resources » Here
By Joannès Vermorel, July 2016

The convolution power is a relatively advanced mathematical operation. In supply chain, convolution power can be used to scale probabilistic demand forecasts up or down. Convolution power offers the possibility to perform linear-like numeric adjustments on probabilistic forecasts. Furthermore, convolution power can be interpreted as the probabilistic counterpart of the linear adjustments performed on "classic" forecasts - i.e. periodic forecasts regressed against the mean or the median.


Advanced functions

cumsub(G.Item, G.Stock, G.Quantity, G.Rank)

takes 4 vectors belonging to a grid table with: G.Item the item identifier, all lines that share the same value belong to the same item; G.Stock the initial stock for the item, all lines that belong to the same item must have the same G.Stock value; G.Quantity the quantity of the item required for the purchase of the grid line; G.Rank a bundle identifier, all lines that share the same bundle identifier belong to the same bundle, it is forbidden to have two lines with the same (G.Item, G.Rank) pair, and all bundles are ordered by increasing rank. The function cumsub() explores all bundles by increasing rank, keeping track of the remaining stock for each item. Initially, this stock is defined by the G.Stock vector. For each bundle, the function determines whether there is enough remaining stock to purchase all grid lines in that bundled, based on whether the stock exceeds G.Quantity. If that is the case, then the function decrements the stock for each item, and writes to each grid line the remaining stock for that item. If there is not enough stock to serve the entire bundle - usually because one of the item has run out - then the function does not update the remain stocks and stores for each grid line the value -(S+1) (where S is the remaining stock for that item at that point), to indicate both that the grid line is not purchased (test if G.S < 0) and whether it was that specific line that caused the bundle not to be purchased (test if G.Quantity + G.S + 1 > 0) and by how much (G.Missing = G.Quantity + G.S + 1).

forex(value, Origin, Destination, date)

Returns the amount expressed in the currency Origin into the equivalent amount in the currency Destination according to the historical rates at the specified date. The currencies should be encoded with their canonical three-letter codes. Lokad supports about 30 currencies leveraging the data provided by the European Central Bank. Rates are updated on a daily basis. See also isCurrency() to test the validity of your currency code.

hash(value)

Returns a pseudo-injective hash value between 0 and 2^24-1. This function is typically used to randomly shuffle a dataset by hashing the content of a column, and then sorting against the hashed values.

isCurrency(currencyCode)

Returns true if the text entry passed as argument is a currency code recognized by the forex() function.

mkuid(X, offset)

Returns a unique number, with unicity maintained across Envision runs. This function is intended to uniquely identify results calculated by Lokad. For example, it can be used to generate a unique purchase order number to be incremented whenever the Envision script is re-executed. The vector X is ignored, but the UID (unique identifier) is generated as a scalar in the table associated to X. The offset is an optional scalar that represents the starting suffix for for the UID. The generated strings are numbers in format PPPPPPPAAA, with P a page number (does not start with 0) that is always strictly increasing, and A an incremented counter that starts at offset (or 0 if no offset parameter is provided). P has at least 7 digits, A has at least 3. The UIDs offer three properties. (1) All UIDs can be parsed as numbers, and those numbers will be different. Keep in mind, however, that UIDs have at least 10 digits, and likely more if each call needs to generate more than 1000. (2) An UID generated at time T is strictly inferior (in alphabetical order) to an UID generated at time T' > T. (3) If all calls generate similar numbers of UIDs (less than 999, or between 1000 and 9999, etc.) then the previous property is also true for the numeric order between UIDs.

solve.moq(...)

An advance numeric solver for the general MOQ problem (minimal order quantities).

pricebrk(D, P, Prices.MinQ, Prices.P, Stock, StockP)

Returns returns the distribution of the marginal purchase unit price. See Supplier Price Breaks.

priopack(V, MaxV, JT, B) by [Group] sort [Order]

A simple variant of the bin packing algorithm intended to be used with purchase prioritization list. Unlike the classic bin packing algorithm, not only, we seek to optimize the bin capacities, but the ordering of the units should also preserved as much as possible. Order contains the ranks of the lines to be packed. V is the volume of each line. Group is the equivalence class of the suppliers, with bin packing computed per supplier. MaxV is the max volume capacity, its value is homogeneous to V, and it is assumed to be a constant value across the equivalent class Group. JT is the jumping threshold, its values is homogeneous to V, it is typically expected to a small multiple of the Group value. B is an optional argument interpreted as the barrier; when this value is provided, the bin-packing process is not allowed to reorder lines that below to the same equivalence class as defined by B.

smudge(values, present) by [Group] sort [Order]

Takes an incomplete vector of values and a boolean vector that determines where the valid values are present. It returns a full vector of valid values, that has been completed by spreading valid values into the non-valid ones. More precisely, the output vector is built by looking at every line, group by group (if there is a Group argument) and following the ascending Order, and replacing any non-valid value by the last value that has been seen or by a default value if no valid value has been seen yet in the group.

stockrwd.m(D, AM), stockrwd.s(D), stockrwd.c(D, AC)

The stock reward functions. These functions are used to build prioritized ordering policy out of the probabilistic forecasts produced by Lokad.

Project timeline: center seems to have an effect



Probabilistic demand forecasts are particularly suitable for optimizing decisions while taking supply chain risks into account. However, unlike classic forecasts where the demand is expressed as a definite quantity associated with a specific period of time, probabilistic forecasts involve distributions of probabilities.

<center>[image||{UP}/Resources/project-timeline.svg]</center>

Image


While distributions provide more insights about the future compared to single-point indicators, distributions are more complex to manipulate. Such manipulations may be required to reflect market evolutions that cannot be inferred from historical data. The convolution power is a mathematical operation that allows to scale a distribution of probabilities in a pseudo-linear fashion.

[image||{UP}/Resources/project-timeline.svg]

Image

For example, if a retailer knows that each promotion will bring a 100% increase in sales, then, all it takes to adjust a classic demand forecast - which ignores promotions - is to multiply the original number by 2. In the case of probabilistic forecasts (which also ignores promotions), it's not possible to multiply the distribution by 2 in the naive sense because the sum of the distribution needs to remain equal to 1 and represent the sum of the probabilities.

Basic concepts: center not needed

In order to get anything out of Envision, Lokad needs to be fed with the historical data of your business. This data is expected to be provided in tabular file format, and Envision supports a wide spectrum of data formats such as CSV or Excel sheets. Your Lokad account is bundled with an online file repository, and the input data files are expected to be stored within your Lokad account.

Lokad already supports many well-known commerce management software connectors. Thus, if your system happens to be already supported by Lokad, in this case, you only need to grant Lokad an access to your system. Lokad will take care of importing all the relevant data and the corresponding tabular files will be created directly within your account. These files are then ready for immediate consumption by Envision.

Image


If Lokad does not yet support the software where your data is currently located, then it is still possible to perform an ad-hoc data extraction, typically by querying the database, and then importing the files into Lokad using FTP (File Transfer Protocol) or its variants like SFTP. Lokad also supports manual uploads through the web, but our experience indicates that if data extraction cannot be automated, re-uploading your most recent data every time tends to be fairly tedious.

In order to get anything out of Envision, Lokad needs to be fed with the historical data of your business. This data is expected to be provided in tabular file format, and Envision supports a wide spectrum of data formats such as CSV or Excel sheets. Your Lokad account is bundled with an online file repository, and the input data files are expected to be stored within your Lokad account.

Lokad already supports many well-known commerce management software connectors. Thus, if your system happens to be already supported by Lokad, in this case, you only need to grant Lokad an access to your system. Lokad will take care of importing all the relevant data and the corresponding tabular files will be created directly within your account. These files are then ready for immediate consumption by Envision.

Image

If Lokad does not yet support the software where your data is currently located, then it is still possible to perform an ad-hoc data extraction, typically by querying the database, and then importing the files into Lokad using FTP (File Transfer Protocol) or its variants like SFTP. Lokad also supports manual uploads through the web, but our experience indicates that if data extraction cannot be automated, re-uploading your most recent data every time tends to be fairly tedious.

Lead times: center changes (similar for the 3 images)

The quantile forecast used to generate the reorder point interprets the lead time as the segment to cover starting from the end of the historical data. Indeed, Lokad defines the “present” as the end of the data. Hence, the forecast starts where the data stop.

Image


In the illustration here above, we have a lead time equal to 4 days. It means that if Lokad computes a reorder point with this lead time, and say, a service level of 95%, the reorder point will be the minimal inventory value - as forecasted by Lokad - that is sufficient to cover the fluctuation of the future demand so that 95% of the time, the reorder point is higher than the demand (hence avoiding the stock-out).

The quantile forecast used to generate the reorder point interprets the lead time as the segment to cover starting from the end of the historical data. Indeed, Lokad defines the “present” as the end of the data. Hence, the forecast starts where the data stop.

Image

In the illustration here above, we have a lead time equal to 4 days. It means that if Lokad computes a reorder point with this lead time, and say, a service level of 95%, the reorder point will be the minimal inventory value - as forecasted by Lokad - that is sufficient to cover the fluctuation of the future demand so that 95% of the time, the reorder point is higher than the demand (hence avoiding the stock-out).

Fractional exponents

Convolution power, as introduced in the previous section, is defined for non-negative integers used as exponents. However, from a practical perspective, it is desirable to have fractional exponents. For example, if the promotional uplift is only 50%, then, we would seek to apply convolution power with $n=1.5$ instead. Here, we generalize the convolution power to arbitrary positive real numbers to be used as exponents.

For $a$, a non-negative real number, we re-define the convolution power as follows:

$$ x^{*a} = \mathcal{Z}^{-1} \Big\{ \mathcal{Z}\{x\}^a \Big\} $$ where $\mathcal{Z}$ is Z-transform of the discrete distribution $x$, defined as: $$ \mathcal{Z}\{x\} : z \to \sum_{k=-\infty}^{\infty} x[k] z^{-k} $$ and where $\mathcal{Z}\{x\}^a$ is the point-wise power over the Z-transform defined as: $$ \mathcal{Z}\{x\}^a : z \to \left( \sum_{k=-\infty}^{\infty} x[k] z^{-k} \right)^a $$ Finally, $\mathcal{Z}^{-1}$ is the inverse Z-transform $$ \mathcal{Z}^{-1} \{X(z) \}= \frac{1}{2 \pi j} \oint_{C} X(z) z^{n-1} dz $$ with $X(z) = \mathcal{Z}\{x\}(z)$, introduced for the sake of readability, and where $C$ is a counterclockwise closed path encircling the origin.

If $a$ is an integer, then the two definitions given above for the convolution power coincide.

In practice, the inverse Z-transform is not always defined. However, there are ways to generalize the notion of Z-transform inversion - somewhat similar to the notion of matrix pseudo inverse used in linear algebra. Details relating to Z-transform pseudo inverse go beyond of the scope of the present document.

Through this Z-transform pseudo inverse, the convolution power can be defined for all random variables of compact support, and for any non-negative real number used as the exponent.

Envision syntax

Envision, the programming language of Lokad, provides an implementation of the general convolution power. The convolution power is accessible through the ^* operator.
y := poisson(3) ^* 4.2 // fractional exponent
The script above illustrates how a Poisson distribution, obtained through the poisson() function, can be convoluted to the power of 4.2.

For $x$ a function $\mathbb{Z} \to \mathbb{R}$ and $y$ a function $\mathbb{N} \to \mathbb{R}$, we can define the convolution power of $x$ by $y$ with: $$ x^{*y} = \sum_{k=0}^{\infty} y[k] x^{*k} $$ Envision also supports this alternative expression of the convolution power through the ^* operator, as illustrated by the script below.
y := poisson(3) ^* exponential(0.05)
The exponent is an exponential distribution obtained by using the exponential() function.

Use case: aerospace spare parts

Let's consider an airline company that operates a homogeneous fleet of 100 aircraft. The company needs to optimize its inventory of APUs (auxiliary power units) which happen to be an expensive repairable component required by the aircraft. The demand for APUs has been forecast for the horizon of interest as a probabilistic demand forecast $X$.

Now, this company has the opportunity to buy a small competitor operating 5 aircraft that are homogeneous to our company's own fleet. Through this competitor acquisition, the company gains extra aircraft and extra passengers. If we assume that all aircraft are statistically independent in their need for APUs, and if we assume that the competitor's aircraft have similar needs to the ones of the acquiring company, then, the total demand for APUs for the merged entity can be revised as $X^{*\frac{100 + 5}{100}}=X^{*1.05}$.

References