# Inventory Control

We consider the problem where there is an amount of stock $x_t$ at time $t$. You can perform the action to order $a_t$ units of stock. Further the demand at time $t$ is $d_t$. We assume $d_t$ is independent over $t$. The change in the amount of stock follows the dynamic:

It is possible for $x_t$ to be negative, which corresponds to backordered stock.

There is a cost for ordering $a \in \mathbb R$ units of stock:

Note here $c(a)=0$ if $a=0$. There is a cost $\kappa(x)$ for holding stock when $x>0$ or for unmet demand when $x<0$. Specifically

for positive constants $h$ and $p$. If we consider the minimization problem over $T$ time steps then we have a dynamic program:

The Bellman equation for this optimization problem is

Here $y=x+a$. If we define $B(x)$ as follows

then (removing the subscript $t$ for now) notice the above Bellman Equation becomes

There exists an explicit closed form solution to this optimization. Specifically there exists values $s$ and $S$ such that if the stock level goes below $s$ then we order enough to have $S$ units of stock. (We will show that $S$ minimizes $B(x)$ and $s$ is such that $B(s) = K+B(S)$.)

We give a proof for the case where $K=0$. This gives the necessary intuition for the more general case where $K>0$, which we subsequently discuss. (The formal argument is given in a series of exercises: Ex 2–Ex 4.)

## $S$-Inventory control.

We consider the equation with $K=0$. Notice if $B(x)$ is convex and $B(x) \rightarrow\infty$ as $|x|\rightarrow\infty$ then $S$, the minimum of $B$, is finite. Thus from it holds that:

Notice if $B(x)$ is convex then relatively straight forward to check that $L(x)$ is convex and $L(x)\rightarrow\infty$ and $|x| \rightarrow \infty$ (see Ex [sS:Ex0]). Also see the following Figure:

Figure: $B(x)$ and $L(x)$ for $K=0$.

Further, if, given the function $L(x)$ above, we now update $B(x)$ by taking

then it is straight-forward to check that the new function $B$ is also convex and $B(x)\rightarrow \infty$ as $|x| \rightarrow\infty$ (see Ex [sS:Ex0]).

Thus (putting sub-script $t$ back and noting that $L_0(x)$ is convex) we see that the sequence of functions $L_t(x)$ and $B_t(x)$ are convex and that $S_t$, the minimum of $B_t(x)$, defines the optimal control

• If $x < S_t$ then order so you have $S_t$ units of stock, $x+a = S_t$ .
• If $x \geq S_t$ then do nothing.

## $(s,S)$-Inventory control.

We consider the equation with $K>0$. That is

In general $B(x)$ will not be convex, but let’s assume it is for a moment in order to gain intuition. Again let $S$ be the minimum of $B(x)$. In this case the minimization over $y >x$ above is solved at $y=S$ if $x\leq S$ and $y=x$ if $x>S$. (Note if $y=x$ in it is obviously better to take $B(x)$ rather than $B(x)+K$.) So we have that

Now assuming $B(x)$ is continuous then there will be a value of $x=s < S$ such that This will be the point for which for $x < s$ then $K+B(S)$ is the minimum in , while for $x \geq s$, $B(x)$ will be the minimum in . I.e. In this case the optimal control will be

For a convex function $B(x)$ we plot $L(x) +ca$ in Figure [sS:Fig2]. Notice that $L(x)$ is clearly not convex. Essentially, the additional $K$ term has introduced a “bump” of size $K$. So rather than assume convexity motivates, this motivates the idea of $K$-convexity.

Definition [$K$-convex] A function $B$ is $K$-convex if

Remark. The definition above is not terribly intuitive. It can be shown that $K$-convexity means that for $x the line segment from $(z,B(z)+K)$ to $(x,B(x))$ does not intersect $(y,B(y))$ for any value of $y$ between $x$ and $z$. I.e. if you are standing at point $(z,B(z)+K)$ you have an unobstructed view of $(x,B(x))$.

If $B(x)$ is $K$-convex then we can show that is solved by , just like in the convex case. (This is Ex [sS:Ex1].) Further, we can show that if $B(x)$ is $K$-convex then $L(x)$ defined by is $K$-convex. (This is Ex [sS:Ex3]). Thus it can be shown that when we update $B(x)$ according to the rule

then $B$ is also $K$-convex. (This is Ex [sS:Ex2].)

## Exercises

Ex 1. a) Given $B(x)$ is convex and $B(x) \rightarrow\infty$ for $|x|\rightarrow\infty$, show that

is such that $L(x)$ is convex and $L(x) \rightarrow\infty$ for $|x|\rightarrow\infty$.
b) Given $L(x)$ is convex and $L(x) \rightarrow\infty$ for $|x|\rightarrow\infty$, show that

is such that $B(x)$ is convex and $B(x) \rightarrow\infty$ for $|x|\rightarrow\infty$.

Ex 2. We let $B(x)$ be $K$-convex, continuous with $B(x) \rightarrow \infty$ as $|x|\rightarrow\infty$. Also let $S= \min B(x)$ and $s$ is the smallest number such that $B(s) = B(S) + K$.
a) Show that, for $x < s$, $B(x) > B(S)+K$ .
(Hint: show $B(x) > B(s)$.)
b) Show that for $s < x, $B(x) \leq B(y)+K$.
(Hint: consider two cases $x and $x>S$.)
c) Show that :

is solved by :

The following exercise establishes some properties of $K$-convex functions

Ex 3. Show that
a) The sum of $K$-convex functions is $K$-convex.
b) A convex function is $K$-convex.
c) If $B(x)$ is $K$-convex then so is $B(x+a)$ is $K$-convex.
d) The convex combination of $K$-convex functions is $K$-convex.
e) If $B$ is $K$-convex then $\mathbb E_Z [ B(x+ Z)]$ is $K$-convex.

Ex 4.  If we let

where $S$ minimizes $B(x)$ and $s$ is the smallest value such that $B(s) = K + B(S)$. We will show that $L$ is $K$-convex:

Verifying by moving $s$ through the following cases:
a) $s \leq y-b$
b) $y-b and $B(y) \geq B(s)$
c) $y-b and $B(y) < B(s)$
d) $y < s < y+z$
e) $y+z

## References.

The idea of $K$-convexity is due to Scarf. A full account of all the calculations above is given in the excellent text of Bertsekas.

Scarf, Herbert. “The optimality of (5, 5) policies in the dynamic inventory problem.” Optimal pricing, inflation, and the cost of price adjustment (1959).

Bertsekas, Dimitri P. Dynamic programming and optimal control. Vol. 1. No. 2. Belmont, MA: Athena scientific, 1995.