Typical mistakes · In summary¶

25.3 Typical mistakes¶

Warning

Applying the zero-inventory ordering property with capacities. The proof moves production between two periods without limits: with capacities a period can produce while units are in stock.
Computing the cost of a run from scratch. Computing every \(c_{j,t}\) from its definition costs \(O(m^3)\) steps inside the DP algorithm; the incremental computation of CostMatrix keeps \(\Theta(m^2)\).
Forgetting the empty final inventory. The subinstance with periods \(\{1,\dots,t\}\) ends with an empty inventory: this is why the run in period \(j\) produces exactly \(D_{j,t}\) units.
Reading one optimal plan as the only one. Example 25.1 has two optimal plans: the DP algorithm returns the one with the smallest period \(j\), because it updates only on a strictly smaller value.

In summary

If all costs are non-negative, the uncapacitated problem has an optimal plan in which a period produces only when the inventory is zero (Wagner and Whitin), so \(x_j=D_{j,t}\) for every production run.
The cost \(c_{j,t}\) of every run is computed in \(\Theta(m^2)\) steps, and the recurrence \(v(t)=\min_j\{v(j-1)+c_{j,t}\}\) gives the optimal value in \(\Theta(m^2)\) steps; it is a shortest path.
The zero-inventory ordering property rests on production without limits: with capacities it fails.

Dashboard of the example.

Instance	Lower bound	Upper bound	Origin
Example 25.1 (uncapacitated, \(m=5\))	\(170\)	\(170\)	DP algorithm of Wagner and Whitin

Exercises on this chapter: Uncapacitated lot sizing (ULS)