# Inventory planning problem solved through dynamic programming

I am working on problem (15-11) Inventory planning from Introduction to Algorithms (CLRS, 3rd Ed).

15-11: Inventory Planning, p.411

The Rinky Dink Company makes machines that resurface ice rinks. The demand for such products varies from month to month, and so the company needs to develop a strategy to plan its manufacturing given the fluctuating, but predictable, demand. The company wishes to design a plan for the next $$n$$ months. For each month $$i$$, the company knows the demand $$d_i$$, that is, the number of machines that it will sell. Let $$D = \displaystyle\sum_{i=1}^{n} d_i$$ be the total demand over the next $$n$$ months. The company keeps a full-time staff who provide labor to manufacture up to m machines in a given month, it can hire additional, part-time labor, at a cost that works out to c dollars per machine. Furthermore, if, at the end of a month, the company is holding any unsold machines, it must pay inventory costs. The cost for holding j machines is given as a function $$h(j)$$ for $$u = 1, 2, ... , D$$, where $$h(j) \ge 0$$ for $$1 \le j \le D$$ and $$h(j) \le h(j+1)$$ for $$j \le 1 \le D - 1$$.
Give an algorithm that calculates a plan for the company that minimizes its costs while fulfilling all the demand. The running time should be polynomical in $$n$$ and $$D$$.

In other words, problem asks to create dynamic programming algorithm that solves this problem.

So far, I came up the the following solution, and not sure if it is any good.
Optimal sub-problem: Let $$MinCost(i,j)$$ be the function that returns minimized cost of operation for past $$i$$ months, $$j$$ is the number of unsold machines left at the end of the month $$i$$.(Goal, is to calculate $$MinCost(n,0)$$, in other words, at the end of planning period(month $$n$$), there are no unsold machines.)

So, the DP recurrence is given by $$MinCost(0,0) = 0$$ and

$$\quad MinCost(i,j) = \min\{MinCost(i-1,j-k) + c(k,j,i) + h(j) \mid 1 \le k \le D \}$$

for $$i+j > 0$$; here, $$c(k,j,i)$$ is the function that calculates the costs of the production.

If my optimal sub-problem is correct, how do I create an algorithm to solve it?

CLRS give plenty of implementations in their chapter on dynamic programming, e.g. in the section on Rod cutting

• recursive top-down (p363),
• memoized (p365f) and
• bottom-up (p366).

I suggest you try to adapt one of these.

The overal idea of the sub-problem sounds good.

I've noticed a few issues:

##### What is k supposed to represent?

$$j$$ represents the number of machines unsold at the end of month $$i$$. This can't be negative as you cannot have a negative number of machines unsold, which means you sold more than what you produced!

You said you start with $$MinCost(n,0)$$ so you start with $$j=0$$, but then you need to compute $$MinCost(n-1,0-k)$$ and you wrote that $$1 \leq k$$, which leaves to negative $$j$$!. There seem to be an issue here.

I think your idea was that $$k$$ was the net difference of machines unsold on day $$i$$, which makes it hard to reason about.

So let's define $$k$$ as the number of unsold machines at the beginning of month $$i$$ (= number of unsold at the end of month $$i-1$$).

##### What is $$c(k,j,i)$$?

You should have enough data to compute the costs yourself. By the new definition of $$k$$, $$c(k,j,i)= c \cdot (j-k + d_i - m)$$. This is because you had $$k$$ machine at the beginning of month $$i$$, you have $$j$$ machines at the end of that month and you sold $$d_i$$ machines, so you produced $$j-k + d_i$$ machines that month. You can produce $$m$$ machines without any additional cost so the remaining number of machine costs $$c$$ dollars per machine.

Please note that this value cannot be negative, as you can't get back the costs if you have to build less than $$m$$ machines. So $$c(k,j,i)= max(0, c \cdot (j-k + d_i - m))$$.

##### This brings us to

$$\quad MC(i,j) = \min\{MC(i-1,k) + max(0, c \cdot (j-k + d_i - m)) + h(j) \mid 0 \le k \le D \}$$

With $$MC(0, j) = \begin{cases} 0 & \quad \text{if } i = 0\\ + \infty & \quad \text{if } i \neq 0 \end{cases}$$

Because you can't have machines in stock before the first day.

We could make some optimisation on the max value of $$k$$ but it's a bit hard to compute and won't improve the asymptotic complexity.

I believe this should be enough to write the algorithm.

I was visiting the dynamic programming questions in the CLRS the other day, and I saw this problem. I think this can be solved in $$O(nD)$$.

Let $$C(i,j)$$ be the minimum cost of producing a total of $$1 \leq j \leq D$$ machines at the end of $$1 \leq i \leq n$$ months. Since the production must meet the demand, if we have $$j < \sum_{k=1}^i d_k$$ at month $$i$$ (i.e., we couldn't meet the demand), we set $$C(i,j) = \infty$$ since this is not a valid solution. Otherwise, at month $$i$$ to produce $$j$$ machines, where $$j \geq \sum_{k=1}^i d_k$$, we have the choice of producing $$l \leq j$$ machines in $$i-1$$ months and $$j-l$$ machines this month. The optimal cost of the former is given by $$C(i-1,l)$$ and the cost of the latter is $$c \cdot (j-l-m)$$. Since this value cannot be negative, we can rewrite it as $$c \cdot max(0, (j-l-m))$$, which makes the cost $$0$$ if it is negative. We also need to store the extra produced machines that are over the demand in an inventory, whose cost is $$h(j-\sum_{k=1}^i d_k)$$. This must be added to the cost above. Let $$C$$ be an $$(n+1) \times D$$ matrix. We also compute the cumulative summation of demands in an array $$A$$ to help checking whether we meet the demand in a particular month. Then the recursive formulation becomes:

$$$$C(i,j) = \begin{cases} 0, & \text{if } i=0 \\ \infty, & \text{if } j < A[i] \\ min_{1\leq k \leq j} (C(i-1,k) + (c \cdot max((j-k-m),0)) + h(j-A[i])), & \text{otherwise} \end{cases}$$$$

The above formulation looks like $$O(nD^2)$$. But assume we computed $$C(i,j)$$ and this cell chose some $$k$$ in row $$i-1$$ as minimum. While computing $$C(i,j+1)$$ the minimum cell in the above row for it must either be again $$k$$ (i.e., $$C(i-1,k)$$) or $$C(i-1,j+1)$$. The former is because $$h(j) \leq h(j+1)$$ and we would choose the same minimum in the above row when computing for $$j+1$$ if we did not consider $$C(i-1,j+1)$$. By keeping a running minimum for row $$i-1$$, thus the runtime can be reduced to $$O(nD)$$.