Inventory and Supply Chain

Motivation

The continuous-review $(Q, r)$ policy is the standard replenishment rule of inventory theory: whenever the inventory position (stock on hand plus on order minus backorders) drops to the reorder point $r$, order a fixed order quantity $Q$. It is used in practice and taught in every operations management course, usually after the deterministic economic order quantity (EOQ) model, which is the same system with a constant demand stream.

Practitioners and textbooks rely on a robustness property of the EOQ: its cost is very insensitive to the choice of order quantity. If the order quantity is off by a factor $\alpha$, the cost rises only by the factor $\tfrac12(\alpha + 1/\alpha)$; ordering 50% too much costs about 8% extra. The insensitivity of the stochastic $(Q, r)$ system to its control parameters had been observed numerically (Wagner, O'Hagan and Lundh 1965; Naddor 1975; Archibald and Silver 1978), but, as Zheng notes, no analytical result on it was known.

Timeline:

• 1963: Hadley and Whitin derive the $(Q, r)$ cost for Poisson demand.
• 1986: Zipkin proves that the average backorders of a $(Q,r)$ policy are jointly convex in $(Q, r)$ under continuous demand (Zipkin 1986).
• 1992: Zheng derives simple optimality conditions for the continuous $(Q, r)$ model and compares it with the EOQ model under the same cost structure. One of the results is that the stochastic cost curve is flatter in the order quantity than the EOQ curve (Zheng 1992). This mission formalizes that result.

Setting

Demands arrive at rate $\lambda>0$; orders arrive after a fixed leadtime $L>0$; all stockouts are backordered. Each order costs $K>0$; holding costs accrue at rate $h>0$ per unit in stock and penalty costs at rate $p>0$ per unit backordered. The leadtime demand $D\ge 0$ has distribution $\mu$ with finite mean $E(D) = \lambda L$.

The inventory cost rate at inventory position $y$ is

$$G(y) = E\big[h(y-D)^+ + p(D-y)^+\big],$$

assumed to attain its minimum at a unique point $y^0$. The long-run average cost of the policy $(Q, r)$ is

$$c(Q, r) = \frac{\lambda K + \int_r^{r+Q} G(y)\,dy}{Q}, \qquad Q>0.$$

For fixed $Q>0$ let $r(Q)$ be a reorder point minimizing $c(Q,\cdot)$, and let

$$C(Q) = c(Q, r(Q)), \qquad H(Q) = G(r(Q))\ (Q>0), \quad H(0) = G(y^0).$$

$C$ is the cost of the order quantity $Q$ when the reorder point is always chosen optimally for it. An optimal order quantity $Q^*$ minimizes $C$ over $Q>0$, and $C^* = C(Q^*)$.

The EOQ model is the same system with the constant leadtime demand $\lambda L$. Its cost rate is $G_d(y) = h(y-\lambda L)^+ + p(\lambda L-y)^+$, and $r_d$, $H_d$, $C_d$ are the objects above at $G_d$, with optimum $Q^*_d$ and $C^*_d$.

Formalization targets

Goal: Theorem 4

$$\frac{C(\alpha Q^*)}{C^*} \le \frac12\left(\alpha + \frac1\alpha\right) \qquad \forall \alpha>0.$$

The goal holds for every demand distribution satisfying the standing assumptions and every optimal $Q^*$. Both regimes, $\alpha<1$ and $\alpha>1$, are included.

Milestones

In the order the proof uses them:

1. Eq. (7): $\int_{r(Q)}^{r(Q)+Q} G = \int_0^Q H$, hence $C(Q) = \big(\lambda K + \int_0^Q H(y)dy\big)/Q$ for $Q>0$.
2. Lemma 4: $H$ is increasing and convex on $[0,\infty)$ with asymptotic slope $hp/(h+p)$.
3. Eq. (8): an optimal $Q^*$ exists, and $Q>0$ is optimal iff $H(Q) = C(Q)$.
4. Eq. (18): $H_d(Q) = \frac{hp}{h+p}Q$, with $r_d(Q) = \lambda L - \frac{h}{h+p}Q$.
5. Lemma 7: $H_0(Q) \le H_d(Q) \le H(Q)$ and $A(Q)\le A_d(Q)$, where $H_0 = H - G(y^0)$ and $A(Q) = QH(Q) - \int_0^Q H$.
6. Eqs. (26)–(27): $H(\alpha Q)\le \alpha H(Q)$ for $\alpha>1$ and $H(\alpha Q)\ge\alpha H(Q)$ for $0<\alpha<1$.
7. Lemma 9: $\int_Q^{\alpha Q} H(y)\,dy \le \frac{\alpha^2-1}{2}\,Q H(Q)$ for all $\alpha>0$, $Q>0$.

Significance

In the EOQ model the relative cost of a scaled order quantity is exactly $C_d(\alpha Q^*_d)/C^*_d = \tfrac12(\alpha + 1/\alpha)$ (Eq. (25) of the paper). Theorem 4 shows that the stochastic system is at least as forgiving. The bound holds for every leadtime-demand distribution with a unique newsvendor minimizer, and it does not depend on the parameters $K$, $h$, $p$, $\lambda$ or $L$. Because the reorder point is re-optimized for each quantity, the bound applies to the practical question of how much a misestimated lot size costs when the safety stock is set correctly.

Together with the other results of the paper (the $1/8$ bound for the EOQ heuristic and the bounds between $Q^*$ and $Q^*_d$, which are separate missions of this series), it gives a closed-form account of why the EOQ is a good heuristic for stochastic systems.

The result has a complete published proof. It has not been machine-checked. The work that remains is a formal proof for general distributions: the paper differentiates $G$ and $r(Q)$ twice, and a formal proof has to replace those derivatives with arguments that need no density.

Difficulty

$C(Q)$ is defined through an inner minimization over the reorder point, so its shape in $Q$ is controlled by the implicitly defined function $H(Q) = G(r(Q))$ rather than by $G$ directly. The obvious approach would bound $C(\alpha Q^*)$ with the reorder point fixed at $r(Q^*)$. That approach is the wrong comparison: it bounds a larger quantity, and the resulting bound depends on the distribution.

The paper's proof uses three properties of $H$: that it is convex, that its slope never exceeds the EOQ slope $hp/(h+p)$, and that it dominates $H_d$. The paper obtains these from the derivatives $r'(Q)$ and $H'(Q)$ under a smooth demand distribution. Without a density, $r(Q)$ is only an argmin and $H$ need not be differentiable, so none of these three properties can be read off a derivative formula; the asymptotic slope in particular depends on the finite mean $E(D) = \lambda L$ and on the behaviour of $G$ at $\pm\infty$.

Formalization scope

The mission is set in Lean 4 with Mathlib. All objects are real valued.

• Model. The structure QRModel bundles $\lambda, L, K, h, p>0$, a probability measure $\mu$ on $\mathbb{R}$ with integrable identity, $\int x\,d\mu = \lambda L$, $D\ge 0$ almost surely, and the unique-minimizer hypothesis on $G$. $K>0$ is implicit in the paper and made explicit here. No density is assumed; deterministic and discrete demands are allowed, and the paper's own numerical study uses Poisson demand.
• Generic machinery. $c$, $r(Q)$, $y^0$, $H$, $H_0$, $C$ and $A$ are defined for an arbitrary cost rate and instantiated at $G$ and at $G_d$. $r(Q)$ and $y^0$ are chosen minimizers; they are never defined by the equation $G(r) = G(r+Q)$, which is a lemma of the paper. $H(0) = G(y^0)$. Values at $Q<0$ (and of $c$, $C$ at $Q\le 0$) are junk, and every statement restricts to $Q>0$ or $Q\ge 0$.
• Readings of informal words. "Increasing" in Lemma 4 is strict on $[0,\infty)$, since the proof shows $H'>0$. "Asymptotic slope $hp/(h+p)$" is stated as $H(Q)/Q\to hp/(h+p)$ together with the chord bound $H(Q_2)-H(Q_1)\le \frac{hp}{h+p}(Q_2-Q_1)$ for $0\le Q_1\le Q_2$. The chord bound is the derivative-free form of $H'\le hp/(h+p)$ that the proofs of Lemmas 7–9 use. "The optimal order quantity" is IsOptQty Q, meaning $Q>0$ and $C(Q)\le C(Q')$ for all $Q'>0$. Its existence is asserted in the Eq. (8) milestone, so the goal is not vacuous. "$\forall\alpha>0$" is a real $\alpha>0$ with real division $1/\alpha$. In Lemma 9 the integral $\int_Q^{\alpha Q}$ is oriented, as on the page.
• Ruling out trivializations. $C(\alpha Q^*)$ re-optimizes the reorder point for $\alpha Q^*$; holding it at $r(Q^*)$ would be a different theorem. $C^*>0$ is a consequence of the model, not a hypothesis.

A complete development needs the following:

• integrability and continuity of $G$;
• existence of the optimal reorder point;
• convexity of $H$;
• the asymptotics $G - G_d\to 0$ at $\pm\infty$;
• Jensen's inequality $G_d\le G$ (Eq. (22));
• existence of $Q^*$.

These facts about newsvendor cost functions are reusable in the other missions of this series. Contributions of any of them as separate lemmas are welcome.

Selected references

• Y.-S. Zheng, On Properties of Stochastic Inventory Systems, Management Science 38(1):87–103, 1992. https://doi.org/10.1287/mnsc.38.1.87
• P. H. Zipkin, Inventory Service-Level Measures: Convexity and Approximation, Management Science 32(8):975–981, 1986. https://doi.org/10.1287/mnsc.32.8.975
• G. Hadley and T. M. Whitin, Analysis of Inventory Systems, Prentice-Hall, 1963.
• H. M. Wagner, M. O'Hagan and B. Lundh, An Empirical Study of Exactly and Approximately Optimal Inventory Policies, Management Science 11(7):690–723, 1965. https://doi.org/10.1287/mnsc.11.7.690
• A. Federgruen and Y.-S. Zheng, An Efficient Algorithm for Computing an Optimal (r, Q) Policy in Continuous Review Stochastic Inventory Systems, Operations Research 40(4):808–813, 1992. https://doi.org/10.1287/opre.40.4.808

Motivation

Many firms learn about demand before it has to be served: customers place orders days or weeks ahead of the date they want delivery. Gallego and Özer (Management Science 47(10), 2001) model this advance demand information in a periodic-review inventory system and ask how the optimal replenishment policy should use it. Classical inventory theory (Arrow, Harris and Marschak 1951; Scarf 1959; Veinott 1965, 1966; Iglehart 1963) assumes that nothing about future demand is known when an order is placed. With advance orders the state of the system is no longer a single number, and it is not a priori clear whether the familiar policy structures survive.

This mission covers the paper's zero set-up cost case (Section 5). The companion mission Integrating Replenishment Decisions with Advance Demand Information I covers the positive set-up cost case and its $(s, S)$ policies.

Setting

Time is divided into periods $t = 1, \dots, T$. The supply lead time is an integer $L \ge 0$, and the information horizon is $N$. In period $t$ customers place orders $D_t = (D_{t,t}, \dots, D_{t,t+N})$, where $D_{t,s} \ge 0$ is demand placed in period $t$ for delivery in period $s$. Throughout, $N > L + 1$; write $M = N - L - 1 \ge 1$.

At the start of period $t$ the decision maker knows two things. The first is the modified inventory position $x_t$: on-hand stock plus outstanding orders minus backorders, net of the demand already observed for the protection period $t, \dots, t+L$. The second is the vector

$$o_t = (o_{t,t+L+1}, \dots, o_{t,t+N-1}) \in \mathbb{R}^M$$

of demands already observed for periods beyond the protection period. The decision maker raises the position to $y \ge x_t$ at zero fixed cost, the demand vector $D_t$ is realised, and the state moves to

$$x_{t+1} = y - \sum_{k=0}^{L+1} D_{t,t+k} - o_{t,t+L+1}, \qquad o_{t+1,s} = o_{t,s} + D_{t,s}\ (s = t+L+2, \dots, t+N),$$

with $o_{t,t+N} = 0$.

Costs enter through a single-period cost $G_t : \mathbb{R} \to \mathbb{R}$ (holding, backorder and linear ordering cost, charged against the demand over the protection period) and one-period discount factors $\alpha_{t+1} > 0$. The optimal cost-to-go $J_t$ and the cost $V_t$ of ordering up to $y$ satisfy

$$J_t(x, o) = \min_{y \ge x} V_t(y, o), \qquad V_t(y, o) = G_t(y) + \alpha_{t+1}\,\mathbb{E}\,J_{t+1}(x_{t+1}, o_{t+1}), \qquad J_{T+1} \equiv 0,$$

where the expectation is over $D_t$. The base-stock level in period $t$ is the smallest minimizer

$$y_t(o) = \min\{y : V_t(y, o) = \min_x V_t(x, o)\},$$

and the myopic level is the smallest minimizer of the single-period cost,

$$y^m_t = \min\{y : G_t(y) = \min_x G_t(x)\}.$$

A function $f(x, \theta)$ has decreasing differences if $f(x_1, \theta) - f(x_2, \theta) \le f(x_1, \theta') - f(x_2, \theta')$ whenever $x_1 \ge x_2$ and $\theta \ge \theta'$ componentwise.

Formalization targets

Goal: Theorem 5 (p. 1352)

If $t \mapsto y^m_t$ is nondecreasing on $\{1, \dots, T\}$, then for every period $t$ and every observed-demand vector $o \ge 0$,

$$y_t(o) = y^m_t .$$

The optimal order-up-to level then ignores all advance information beyond the protection period. A second item states the paper's stationary special case: if $G_t = G$ for all $t$, the smallest minimizer $y^m$ of $G$ is the optimal base-stock level in every period.

Milestones: Theorem 4 (p. 1351)

For every period $t$ and every fixed $o_t$:

1. $V_t(\cdot, o_t)$ is convex and $V_t(x, o_t) \to \infty$ as $|x| \to \infty$;
2. $y_t(o_t)$ exists and $J_t(x, o_t) = V_t(\max(y_t(o_t), x), o_t)$: a state-dependent base-stock policy is optimal;
3. $J_t(\cdot, o_t)$ is nondecreasing and convex;
4. $V_t(x, o)$ has decreasing differences in $(x, o)$;
5. $J_t(x, o)$ has decreasing differences in $(x, o)$;
6. $y_t(o)$ is nondecreasing in $o$.

Parts 1–3 are what the goal's proof uses. Parts 4–6 are the paper's second zero set-up result, monotonicity of the base-stock level in observed demand.

Significance

The theorem identifies when advance demand information beyond the protection period can be ignored. When the myopic levels do not decrease over time, which includes stationary costs and ramping-up demand, the $(1 + M)$-dimensional dynamic program collapses to a sequence of one-dimensional newsvendor-type problems. That is both a computational simplification and a managerial statement: information about demand after the protection period does not change the order. Theorem 4, Part 5 gives the complementary monotone comparative statics. When the myopic condition fails, more observed demand never lowers the order-up-to level.

The results are proved in the paper, with the proofs in Appendix B. No machine-checked version exists. This mission produces a formal account of the finite-horizon recursion with a multi-dimensional information state, and checks the base-stock and myopic-optimality arguments against it.

Difficulty

The obvious induction carries convexity of $J_{t+1}$ backward, but here the future cost is evaluated at a random next state $(x_{t+1}, o_{t+1})$ whose first coordinate depends on the current observed demand $o_{t,t+L+1}$. Showing that the base-stock level does not depend on $o_t$ therefore needs more than convexity. It needs to know where $J_{t+1}(\cdot, o_{t+1})$ is flat, uniformly in the random $o_{t+1}$, and that the next position cannot exceed the current order-up-to level. The latter holds only on the reachable states, where observed demands are nonnegative. For a sufficiently negative $o_{t,t+L+1}$ the next period starts above its myopic level whatever is ordered now, and the conclusion fails. On the analytic side, every infimum and expectation in the recursion must be shown to be finite and attained before the order-theoretic argument can start.

Formalization scope

The model is parametrised by $L$ and $M \ge 1$, with $N = L + M + 1$. The demand vector is a function on $\{0, \dots, N\}$ and $o$ a function on $\{0, \dots, M-1\}$, ordered componentwise. $J_t$ is defined by backward recursion with $J_t \equiv 0$ for $t > T$. The minimum over $y \ge x$ is a real infimum and the expectation a Bochner integral against the law $\mu_t$ of $D_t$. Attainment and finiteness are consequences proved in the theorems, not assumptions. Base-stock and myopic levels are characterised as smallest minimizers (IsLeast), never through sInf.

The single-period cost $G_t$ is a primitive rather than being assembled from $c_t$, $g_t$ and the lead-time demand; the paper's $G_t$ has the assumed properties, so the theorems cover the paper's model. Hypotheses the paper uses without stating, all placed on primitives and labelled in the statements:

• nonnegative demands, $D_{t,s} \ge 0$ almost surely;
• coercivity of $G_t$ (the paper states it for $\tilde G_t$ only);
• $\alpha_{t+1} > 0$;
• finiteness of the expectation in (9), guaranteed by linear growth of $G_t$ and finite first moments of $D_t$. This covers piecewise-linear holding and backorder costs with any finite-mean demand (including the paper's Poisson example), but excludes superlinear costs;
• in the goal, $o \ge 0$, the set of reachable states.

The goal cannot be trivialised: the hypotheses are satisfied by concrete instances (for example $G_t(y) = |y|$ with any finite-mean nonnegative demand), and the conclusion identifies the base-stock level exactly rather than asserting that some minimizer exists.

Out of scope: the reduction of the control problem to the functional equation (Appendix A, Özer 2000), the infinite-horizon Theorem 6, and Lemma 5, whose proof argues on the integers and whose real-valued form with a unit forward difference is unverified. Contributions of general lemmas are welcome: convexity and attainment for $\inf_{y \ge x}$ of a convex coercive function, and preservation of convexity and decreasing differences under expectation. All of them are reusable in other inventory models.

Selected references

• G. Gallego, Ö. Özer, Integrating Replenishment Decisions with Advance Demand Information, Management Science 47(10):1344–1360, 2001. https://doi.org/10.1287/mnsc.47.10.1344.10261
• A. F. Veinott, Optimal Policy for a Multi-Product, Dynamic, Nonstationary Inventory Problem, Management Science 12(3):206–222, 1965. https://doi.org/10.1287/mnsc.12.3.206
• D. L. Iglehart, Optimality of (s, S) Policies in the Infinite Horizon Dynamic Inventory Problem, Management Science 9(2):259–267, 1963. https://doi.org/10.1287/mnsc.9.2.259
• D. M. Topkis, Supermodularity and Complementarity, Princeton University Press, 1998. https://doi.org/10.1515/9781400822539

Motivation

In a periodic-review inventory system a manager observes the stock level before ordering, decides how much to order, and then faces random demand. When ordering costs a fixed setup charge plus a constant price per unit, Scarf (1960) proved that an $(s,S)$ policy is optimal in every period of a finite-horizon problem: order up to $S$ when the stock falls below $s$, otherwise order nothing. Real ordering costs are often not of this form. Quantity discounts, a choice between production facilities with different setup and marginal costs, or a supplier whose price schedule falls with volume all give an ordering cost that is concave and increasing but not "setup plus linear". Karlin had analysed the single-period problem with such costs; Porteus (1971) gave the first multiperiod result with random demand.

Timeline:

• Scarf (1960): $(s,S)$ optimality for setup-plus-linear ordering cost, via $K$-convexity of the expected cost-to-go.
• Veinott (1966): an alternative proof of $(s,S)$ optimality under different conditions (quasi-convex one-period costs).
• Porteus (1971): for concave increasing ordering costs and demand with a one-sided Pólya density, a generalized $(s,S)$ policy is optimal in every period; when the cost is piecewise linear with $r$ pieces it is an $(s,S)_r$ policy with at most $r$ reorder levels.

Setting

The ordering cost $c : [0,\infty) \to \mathbb R$ is concave, nondecreasing, and $c(0) = 0$. For $z > 0$, $C_2(z)$ is the supporting line of $c$ at $z$ with the smallest intercept, written as a pair (slope, intercept) $(\kappa, K)$. The set of slopes that occur is $C$, and $K_\kappa$ is the intercept belonging to slope $\kappa \in C$, so $c(z) = \min_{\kappa \in C}\{K_\kappa + \kappa z\}$ for $z > 0$. The limits $(c_0, K_0) = \lim_{z \downarrow 0} C_2(z)$ and $(c_\infty, K_\infty) = \lim_{z\to\infty} C_2(z)$ are assumed to exist.

Demands in successive periods are i.i.d. with density $\varphi$. A function $\varphi$ is $PF_n$ if $0 < \int\varphi < \infty$ and $\det[\varphi(x_i - t_j)]_{i,j\le k} \ge 0$ for all $k \le n$ and increasing $x_1<\dots<x_k$, $t_1<\dots<t_k$; it is a one-sided Pólya density if it is $PF_n$ for every $n$, integrates to $1$ and vanishes on $(-\infty,0)$. Exponential and Erlang densities are examples.

With holding-and-shortage cost $m$ (PF-integrable, bounded below), terminal cost $f_0$, discount factor $0 \le \alpha \le 1$, and convolution $(f*\varphi)(y) = \int f(y-x)\varphi(x)\,dx$, the value functions are

$$h_n = m * \varphi + \alpha\, f_{n-1} * \varphi, \qquad f_n(x) = \inf_{y \ge x}\{c(y-x) + h_n(y)\},$$

where $n$ counts the periods remaining. $Y_n(x)$ is the set of minimizers $S \ge x$. A generalized $(s,S)$ policy is a function $y$ with $y(x) = x$ for $x \ge s$ and $y(z) \ge y(x) \ge S \ge s$ for $z < x < s$: no order above $s$, and below $s$ an order-up-to level that is at least $S$ and does not increase with the starting stock.

Two function classes carry the argument. $f$ is non-$K$-decreasing on $X$ if $f(x) \le f(y) + K$ for $x \le y$ in $X$. For $K \ge 0$, $C_a(K)$ consists of the piecewise continuous, PF-integrable functions with $f(x)\to\infty$ as $|x|\to\infty$ that are nonincreasing on $(-\infty,a)$ or $(-\infty,a]$ and non-$K$-decreasing on the rest of the line. $C(K)$ is its continuous part. With $G_{\kappa n} = \kappa\cdot + h_n$, the assumptions A1–A5 of §VI tie $m$ and $f_0$ to $c_0$, $c_\infty$ and the $K_\kappa$.

Formalization targets

Goal: Theorem 3

Under the standing assumptions and A1–A5, for every $n \ge 1$ the convolution $f_{n-1}*\varphi$ exists and

$$\exists\, s, S,\ \exists\, y \text{ generalized } (s,S) \text{ policy}: \quad y(x) \in Y_n(x) \ \ \forall x \in \mathbb R.$$

The statement fixes no numbers: $s$ and $S$ depend on $n$ and on the data.

Milestones

1. Lemma 9: $\bigcup_a C_a(K)$ equals the class of quasi-$K$-convex, piecewise continuous, PF-integrable functions tending to $\infty$ as $|x| \to \infty$.
2. Lemma 1: every $f \in C(K)$ has reals $s \le S$ with $S$ a global minimizer, $f > f(S) + K$ on $(-\infty,s)$, $f$ nonincreasing there, and $f$ non-$K$-decreasing on $[s,\infty)$.
3. Lemma 5: for continuous $g$, $f(x) = \int_0^\infty g(x-t)\lambda e^{-\lambda t}dt$ is $C^1$ with $f' = \lambda(g-f)$.
4. Lemma 6: $g*\varphi$ is continuous and $C^1$ off a finite set for a one-sided Pólya $\varphi$.
5. Lemma 10 and Theorem 1: $f \in C_a(K) \Rightarrow f*\varphi \in C(K)$, first for exponential $\varphi$, then for every one-sided Pólya density.
6. Theorem 2: if every $G_{\kappa n} \in C(K_\kappa)$ and every $Y_n(x) \ne \emptyset$, a generalized $(s,S)$ policy is optimal in period $n$.
7. Lemma 2: $f_n(x) \le f_n(y) + c(y-x)$ for $x \le y$.
8. Lemma 3: the inductive step producing the hypotheses of Theorem 2 from properties of $f_{n-1}$.

Significance

The result extends $(s,S)$-type structure from setup-plus-linear to arbitrary concave increasing ordering costs, which covers quantity discounts and multi-facility production. When $c$ is piecewise linear with $r$ pieces, the optimal policy is an $(s,S)_r$ policy described by at most $r$ reorder points and order-up-to levels. That is a finite-dimensional family, which makes computing policies tractable. The class $C(K)$ and its closure under Pólya convolution (Theorem 1) are statements about functions of one real variable, independent of the inventory model. Quasi-$K$-convexity extends both $K$-convexity and quasi-convexity (Lemma 8 of the paper).

The theorem is classical and proved on paper; no machine-checked version is known. Its appendix leaves several steps as "easily proved by contradiction", which a formal proof has to fill in. The platform has Bertsekas's $K$-convex $(s,S)$ lemma (BertsekasDP.kconvex_sS_structure, a result about $K$-convex rather than $C(K)$ functions), but no Pólya frequency functions, no quasi-$K$-convexity, and no concave-cost inventory model.

Difficulty

The obvious route copies Scarf: show that the cost-to-go is $K$-convex and that $K$-convexity survives taking expectations. With a concave ordering cost there is no single $K$, and the relevant functions $G_{\kappa n}$ are generally not $K_\kappa$-convex. The weaker property that does hold, membership in $C(K_\kappa)$, is not preserved by convolution with an arbitrary density. It is preserved by one-sided Pólya densities, and Theorem 1 is the step that shows this: exponential kernels come first (via the differential identity (23)), and the general case needs the Schoenberg representation of one-sided Pólya densities as limits of convolutions of exponentials. The second difficulty is combining the different slopes $\kappa \in C$ into one policy (Theorem 2). Separate $(s,S)$ pairs for each $\kappa$ do not by themselves give a monotone policy.

Formalization scope

All functions are ℝ → ℝ; the ordering cost is used only on $[0,\infty)$. The demand density is a function, not a measure; convolution is the Lebesgue integral over $\mathbb R$. $PF_n$ uses Matrix.det over Fin k. The value functions are defined by structural recursion on $n : \mathbb N$ with $f_0$ the terminal cost; $h_n$ is used for $n \ge 1$. $Y_n(x)$ is defined by the optimality inequality, never through the infimum. $G_{\kappa n}$ is defined by the paper's identity (7), $\kappa y + h_n(y)$. $R^- = (-\infty,0)$ is open, and "increasing" is read as nondecreasing. Slopes in $C$ are written $\kappa$ to separate them from the cost function $c$.

Added hypotheses and conventions:

• $m$ piecewise continuous. The paper uses this without stating it (proof of Lemma 3). It is a hypothesis of Lemma 3 and Theorem 3.
• Real-valued $f_n$ in Lemma 2. Following the convention of §X, Lemma 2 assumes each infimum defining $f_n$ is over a set bounded below.
• Measurability of $m$ and $f_0$ (§X) is implied by their piecewise continuity and is not stated separately.

Lean returns $0$ for an infimum over a set unbounded below and for the integral of a non-integrable function. The goal therefore concludes that $f_{n-1}*\varphi$ exists and that $Y_n(x)$ is nonempty (so the infimum is a minimum); it does not assume these. It also does not quantify over arbitrary functions satisfying a Bellman equation or over an arbitrary set-valued $Y$. Everything is built from the data $(c, m, \varphi, \alpha, f_0)$. The class $C(K)$ includes PF-integrability and coercivity, without which Lemma 1 fails.

Welcome contributions: Pólya frequency functions and the exponential special cases (the exponential density is $PF_\infty$), Leibniz-rule lemmas for exponential kernels, the theory of $C(K)$ and quasi-$K$-convex functions (reusable for other inventory models), and a formal Schoenberg representation (Theorem 6 of the paper, cited there and needed for Theorem 1). Theorems 4 and 5 (nonstationary and partial-backlogging extensions) are not part of this mission.

Selected references

• E. L. Porteus, On the Optimality of Generalized (s, S) Policies, Management Science 17(7):411–426, 1971. https://doi.org/10.1287/mnsc.17.7.411
• H. Scarf, The Optimality of (S, s) Policies in the Dynamic Inventory Problem, in Mathematical Methods in the Social Sciences, Stanford University Press, 1960.
• A. F. Veinott Jr., On the Optimality of (s, S) Inventory Policies: New Conditions and a New Proof, SIAM Journal on Applied Mathematics 14(5):1067–1083, 1966. https://doi.org/10.1137/0114086
• I. J. Schoenberg, On Pólya Frequency Functions I. The Totally Positive Functions and their Laplace Transforms, Journal d'Analyse Mathématique 1:331–374, 1951. https://doi.org/10.1007/BF02790092
• S. Karlin, Total Positivity, Volume 1, Stanford University Press, 1968.

Motivation

An inventory manager who stocks many products, faces random demand and pays ordering, holding and shortage costs must decide each period how much of each product to order. In general the optimal decision depends on the whole state and is found by solving a dynamic programme, which becomes impractical as the number of products grows. Myopic (or base stock) policies avoid this: in each period they aim at a target level computed from that period's data alone. Knowing when such a policy is optimal over an infinite horizon tells a practitioner when the multi-period problem decouples into a sequence of one-period problems.

Arthur F. Veinott, Jr. gave such conditions in Optimal Policy for a Multi-Product, Dynamic, Nonstationary Inventory Problem (Management Science 12(3):206–222, 1965). Earlier results of this type were for a single product (the paper cites Karlin, Management Science 6(3), 1960, Bellman–Glicksberg–Gross, Management Science 2(1), 1955, Iglehart–Karlin 1962, and the Arrow–Karlin–Scarf volume of 1958); Veinott's model allows several products, several demand classes, costs and demand distributions that change over time, general ordering constraints and general stock dynamics (backlogging, lost sales, and mixtures), and it does not use the functional equation of dynamic programming. Instead, the proofs analyse the inventory process directly.

Setting

There are $n$ products and $m$ demand classes. Vectors are compared componentwise: $u \le v$ means $u_j \le v_j$ for all $j$. In period $i = 1, 2, \dots$ the manager observes the inventory vector $x_i \in X_i \subseteq \mathbb{R}^n$ (negative coordinates are backlogs) and orders up to a vector $y_i \in Y_i \subseteq \mathbb{R}^n$, subject to $y_i \ge q_i(x_i)$, where $q_i$ is a vector of extended-real functions (for instance $q_i(x) = x$ forbids disposal). A random demand vector $D_i$ with law $\Phi_i$ and values in a Borel set $\mathfrak{D}_i \subseteq \mathbb{R}^m$ then occurs, and the next inventory vector is $x_{i+1} = s_i(y_i, D_i) \in X_{i+1}$. The demands $D_1, D_2, \dots$ are independent. Ordering $y_i - x_i$ costs $c_i \cdot (y_i - x_i)$, the holding and shortage cost is $g_i(y_i, D_i)$, and $\alpha_i \ge 0$ is the discount factor of period $i$.

Regrouping the ordering costs gives the one-period cost

$$W_i(y,t) = c_i\, y + g_i(y,t) - \alpha_i\, c_{i+1}\, s_i(y,t), \qquad G_i(y) = \int_{\mathfrak{D}_i} W_i(y,t)\, d\Phi_i(t),$$

with discount weights $\beta_1 = 1$ and $\beta_i = \alpha_1 \cdots \alpha_{i-1}$. The integrals are assumed finite, and $G_i \ge \gamma_i$ with $\sum_i |\beta_i \gamma_i| < \infty$. An ordering policy $\bar Y$ chooses $y_i$ as a Borel function of the past; it is feasible if $y_i \in Y_i$ and $y_i \ge q_i(x_i)$ for every possible history. Its cost is

$$f(x_1 \mid \bar Y) = \sum_{i=1}^\infty \beta_i\, E\, G_i(y_i) \in (-\infty, +\infty],$$

and a feasible policy of least cost is optimal.

Let $\bar y_i$ minimize $G_i$ over $Y_i$. When $\bar y_i$ is not attainable from $x$, the minimal feasible level $w_i(x)$ is the least element of $Y_i \cap \{y : y \ge q_i(x),\ y \ge \bar y_i\}$. The base stock ordering policy orders up to $\bar y_i$ if $q_i(x_i) \le \bar y_i$ and up to $w_i(x_i)$ otherwise.

Formalization targets

The hypotheses are: (3a) $\bar y_i \in Y_i$ minimizes $G_i$ over $Y_i$; (3b) $q_{i+1}(s_i(\bar y_i, t)) \le \bar y_{i+1}$ for $t \in \mathfrak{D}_i$; (3c) $Y_i$ is closed and linearly ordered by $\le$; (3d) $G_i$ and $s_i(\cdot, t)$ are nondecreasing on $\{y \in Y_i : y \ge \bar y_i\}$, and $q_i$ is nondecreasing where $q_i(x) \not\le \bar y_i$.

Goal: Theorem 3.2

Under (3a)–(3d), the base stock ordering policy

$$\bar Y_i^*(H_i^*) = \begin{cases} \bar y_i, & q_i(x_i^*) \le \bar y_i, \\ w_i(x_i^*), & q_i(x_i^*) \not\le \bar y_i \end{cases}$$

is feasible and optimal: $f(x_1 \mid \bar Y^*) \le f(x_1 \mid \bar Y)$ for every feasible $\bar Y$.

Milestones

1. A nonempty, closed, linearly ordered, bounded-below subset of $\mathbb{R}^n$ has a least element (p. 212); hence $w_i(x)$ exists and equals $\bar y_i$ when $q_i(x) \le \bar y_i$.
2. $w_i$ is nondecreasing where $q_i(x) \not\le \bar y_i$ (p. 214).
3. Once $q_k(x_k^*) \le \bar y_k$, the base stock policy orders up to $\bar y_i$ for all $i \ge k$.
4. Theorem 3.1: under (3a) and (3b), if $q_1(x_1) \le \bar y_1$, ordering up to $\bar y_i$ in every period is optimal, with cost $\sum_i \beta_i G_i(\bar y_i)$.
5. The coupling (3.1): before the first period $T$ with $q_T(x_T^*) \le \bar y_T$,

$$\bar y_i < y_i^* = w_i(x_i^*) \le w_i(x_i) \le y_i.$$

6. Pathwise dominance: $G_i(y_i^*) \le G_i(y_i)$ for every $i$ and every possible demand path.
7. The reduction behind (2.3): $E\, W_i(y_i, D_i) = E\, G_i(y_i)$, by independence of $y_i$ and $D_i$.

Significance

The theorem shows that under (3a)–(3d) the infinite-horizon, nonstationary, multi-product problem is solved by one-period optimization: compute $\bar y_i$ from $G_i$ alone, and when it is unreachable order the least feasible amount. No value function is computed. It covers backlogging and lost sales, products stocked in fixed proportions, and time-varying cost and demand data, and Theorem 3.1 alone settles the frequent case in which the initial stock is small.

The result is proved in the paper. To our knowledge it has not been machine-checked: this mission produces a Lean model of a general stochastic, infinite-horizon, multi-product inventory problem (feasible policies, the expected discounted cost with $+\infty$ allowed), and a checked proof that a myopic policy is optimal in it. The model and its cost are reusable for other base stock and myopic optimality results.

Difficulty

The obvious argument would compare the base stock policy with an arbitrary policy period by period using (3a) alone. That fails once $\bar y_i$ is unreachable. The base stock policy then holds less stock than $\bar y_i$ would require, and it has to be shown that no other policy can reach a lower-cost level later. The proof couples the two trajectories along every demand path, using the monotonicity in (3d) and the linear order of $Y_i$ from (3c), until the base stock level becomes attainable, after which (3b) keeps it attainable. The formal difficulties are:

• the existence and monotonicity of the least element $w_i(x)$ in a closed chain of $\mathbb{R}^n$;
• the measurability of the base stock policy, which is part of its feasibility;
• the passage from pathwise dominance to the expected discounted cost when the cost may be $+\infty$.

Formalization scope

Periods are 0-based in Lean (Lean period $k$ is the paper's period $k+1$). Vectors are Fin n → ℝ with the product order; $q_i$ takes values in Fin n → EReal. Policies are functions of the past demands. The paper shows on p. 219 that this loses no generality once $x_1$ is fixed. The cost is excess, a $[0,\infty]$-valued series of lower Lebesgue integrals of $\beta_i(G_i(y_i) - \gamma_i)$, plus the finite real $\sum_i \beta_i\gamma_i$, taken in EReal. A divergent series therefore gives $+\infty$ and never the junk value $0$. "Minimal element" is IsLeast. The $G_i$ in the statements is the integral of $W_i$ built from the data, and the policy in the goal is constructed from $\bar y$, $q$, $w$ and $s$. Neither is an arbitrary object satisfying the conclusion. The goal concludes optimality, which includes feasibility: a pathwise or conditional statement would not be the theorem.

Hypotheses added relative to the page, each used by the paper without being stated:

• Order feasibility: from every $x \in X_i$ some $y \in Y_i$ with $y \ge q_i(x)$ exists (p. 212 asserts the set defining $w_i(x)$ has a minimal element, which needs it nonempty). The least-element lemma likewise assumes $A$ nonempty.
• (3d)'s $q$-clause in one-sided form: if $x \le x'$ in $X_i$ and $q_i(x) \not\le \bar y_i$, then $q_i(x) \le q_i(x')$. This is the form the proof on p. 214 uses; monotonicity on the region $\{q_i(x) \not\le \bar y_i\}$ alone admits a counterexample to Theorem 3.2.
• Integrability of $W_i(y_i, D_i)$ in the milestone $E W_i = E G_i$.
• Borel measurability of $q_i$ on all of $\mathbb{R}^n$ rather than on $X_i$ (a harmless strengthening).

A complete development needs: least elements of closed chains in $\mathbb{R}^n$; measurability of the least-element selection $x \mapsto w_i(x)$; a Fubini/independence argument for $E\,W_i(y_i,D_i)=E\,G_i(y_i)$; and monotone summation of lower integrals. The least-element lemma and the cost encoding are reusable beyond this mission. Proofs of any milestone are welcome, as are alternative arguments.

Selected references

• A. F. Veinott, Jr., Optimal Policy for a Multi-Product, Dynamic, Nonstationary Inventory Problem, Management Science 12(3):206–222, 1965. https://doi.org/10.1287/mnsc.12.3.206
• R. Bellman, I. Glicksberg, O. Gross, On the Optimal Inventory Equation, Management Science 2(1):83–104, 1955. https://doi.org/10.1287/mnsc.2.1.83
• S. Karlin, Dynamic Inventory Policy with Varying Stochastic Demands, Management Science 6(3):231–258, 1960. https://doi.org/10.1287/mnsc.6.3.231

Motivation

A firm that sells several products must decide, before demand is known, how much production capacity to build and of what kind. Dedicated capacity makes one product; flexible capacity makes any of them. The classic argument for flexibility is demand pooling: capacity that can follow demand to whichever product needs it wastes less than capacity locked to one product (Fine and Freund 1990; Van Mieghem 1998).

When capacity itself is unreliable, as with a supplier that may fail to deliver, a plant that may be disrupted, or a batch that may be rejected, flexibility has a second face. A single flexible resource concentrates the firm's supply in one place, so one failure removes all of it, whereas several dedicated resources rarely fail together. This resource-aggregation effect works against flexibility. Tomlin and Wang (2005) set up a newsvendor network in which both effects are present and ask when a firm should pay more for flexible capacity than for dedicated capacity. Their first answer (Proposition 1) is that a risk-neutral firm facing equal reliabilities and costs never loses by choosing flexibility, whatever the joint distribution of demand. This mission formalizes that answer.

Setting

There are $N$ products with a common unit contribution margin $p>0$. The demand vector $\tilde X=(\tilde X_1,\dots,\tilde X_N)$ is random, nonnegative and integrable; its total is $\tilde X_{N+1}=\tilde X_1+\dots+\tilde X_N$.

Two networks are compared. In the dedicated network SD, resource $n\in\{1,\dots,N\}$ makes only product $n$ and has marginal total cost $c>0$. In the flexible network SF, a single resource, labelled $N+1$, makes every product and has marginal total cost $c_{N+1}$.

Every resource $j$ is unreliable with a Bernoulli yield $\tilde Y_j\in\{0,1\}$, $\mathbb P(\tilde Y_j=1)=\theta$. The common reliability is $\theta\in[0,1]$, the yields are mutually independent, and they are independent of demand. Investing $K_j\ge 0$ in resource $j$ delivers capacity $\tilde Y_jK_j$ and costs $(\lambda+(1-\lambda)\tilde Y_j)c_jK_j$: the firm pays the committed cost $\lambda c_j$ per unit ordered and a further $(1-\lambda)c_j$ per unit delivered, with $\lambda\in[0,1]$.

The realized profits are

$$W^{SD}(K)=\sum_{n=1}^N\Big(-(\lambda+(1-\lambda)\tilde Y_n)cK_n+p\min\{\tilde X_n,\tilde Y_nK_n\}\Big),$$ $$W^{SF}(K_{N+1})=-(\lambda+(1-\lambda)\tilde Y_{N+1})c_{N+1}K_{N+1}+p\min\{\tilde X_{N+1},\tilde Y_{N+1}K_{N+1}\},$$

and a risk-neutral firm maximizes the expected profit $V^{SD}_{RN}(K)=\mathbb E[W^{SD}(K)]$ or $V^{SF}_{RN}(K_{N+1})=\mathbb E[W^{SF}(K_{N+1})]$ over nonnegative investments. Let $V^{SD,*}$ and $V^{SF,*}$ be the optimal values. SF is (weakly) preferred if $V^{SF,*}\ge V^{SD,*}$.

The indifference cost $c^I_{N+1}$ is a value of $c_{N+1}$ at which $V^{SF,*}=V^{SD,*}$, and the flexibility premium is $\Delta=(c^I_{N+1}-c)/c$. The firm prefers SF as long as $c_{N+1}\le(1+\Delta)c$.

The $\alpha$-expected shortfall of a random variable $Z$ is, for $\alpha\in(0,1)$ and the lower quantile $x_{(\alpha)}=\inf\{x:\mathbb P(Z\le x)\ge\alpha\}$,

$$ES_\alpha(Z)=-\frac1\alpha\Big(\mathbb E\big[Z\mathbf 1\{Z\le x_{(\alpha)}\}\big]+x_{(\alpha)}\big(\alpha-\mathbb P(Z\le x_{(\alpha)})\big)\Big).$$

Formalization targets

Goal: Proposition 1

For any demand random vector $\tilde X$:

1. $\Delta_{RN}\ge 0$ for all $0\le\theta\le 1$, that is, SF is preferred whenever $c_{N+1}\le c$;

$$0\le\theta\le\frac{\lambda c}{p-(1-\lambda)c}\ \Longrightarrow\ \Delta_{RN}=0;$$

3. $\Delta_{RN}=0$ if $\rho_X=\mathbf 1$, i.e. all pairwise demand correlations equal $1$.

No distributional form of demand is fixed and no constant is hard-coded beyond the paper's threshold.

Milestones

• (9): the closed form of $V^{SF}_{RN}$.
• (10)–(11), (12)–(13): the optimal investments are critical fractiles

$$F_{X_{N+1}}(K^*_{N+1})=1-\frac{(\lambda+(1-\lambda)\theta)c_{N+1}}{\theta p},\qquad F_{X_n}(K^*_n)=1-\frac{(\lambda+(1-\lambda)\theta)c}{\theta p},$$

and the optimal values are $\theta p$ times partial expectations of demand.

• (A-1) in expected-shortfall form: with $\alpha=1-(\lambda+(1-\lambda)\theta)c/(\theta p)\in(0,1)$,

$$V^{SF,*}\ge V^{SD,*}\ \text{at}\ c_{N+1}=c\iff \alpha\Big(\sum_n ES_\alpha(\tilde X_n)-ES_\alpha\Big(\sum_n\tilde X_n\Big)\Big)\ge 0 .$$

• Subadditivity of $ES_\alpha$ (Acerbi and Tasche 2002).
• The positivity threshold of part 2: investing is worthwhile iff $\theta>\lambda c/(p-(1-\lambda)c)$.
• Correlation $1$ implies $\tilde X_n=a\tilde X_1+b$ with $a>0$, and $ES_\alpha(aX+b)=aES_\alpha(X)-b$.

Significance

Proposition 1 separates the two effects of flexibility under unreliable supply. It shows that for a risk-neutral firm the demand-pooling benefit together with an upside effect of aggregation (one flexible resource succeeds more often than all dedicated ones together) always outweighs the downside aggregation risk. Even with no pooling benefit at all (perfectly correlated demand) the firm is indifferent, not averse. The later results of the paper (loss aversion, CVaR, dual sourcing) are measured against this baseline: a negative premium can appear only once the firm is risk-averse. The expected-shortfall form links newsvendor optimal values to a coherent risk measure, a connection that recurs in inventory risk analysis.

The result is proved in the paper, with a proof that cites Acerbi and Tasche (2002) for two properties of expected shortfall. No machine-checked version exists. A formalization adds three things: a proof for general demand distributions (the paper assumes a joint density and uses the continuous form of expected shortfall); a Lean development of Acerbi–Tasche expected shortfall for general integrable random variables, including subadditivity and affine equivariance; and a reusable model of newsvendor networks with Bernoulli yields and committed costs.

Difficulty

The newsvendor steps (9)–(13) are single-variable concave optimization, but they must be done without a density: the distribution function of total demand may have atoms and flat pieces, so the critical fractile need not be attained or may be attained on an interval, and optimal values must be expressed through lower quantiles. Subadditivity of expected shortfall is the heart of part 1 and is not elementary in the general (atomic) case, which is exactly why the correction term $x_{(\alpha)}(\alpha-\mathbb P(Z\le x_{(\alpha)}))$ appears. Part 3 requires identifying correlation $1$ with almost-sure positive affine dependence, which rests on the equality case of the Cauchy–Schwarz inequality in $L^2$, and then handling nonnegativity constraints on the investments that the affine change of variables may violate. The obvious shortcut of computing everything from densities is not available, because the goal is stated for every demand vector and part 3 is incompatible with a joint density when $N\ge 2$.

Formalization scope

Randomness lives on one probability space $(\Omega,\mu)$; demand is X : Ω → Fin N → ℝ and yields are Y : Ω → Fin (N + 1) → ℝ, where dedicated resource $n$ is Fin.castSucc n and the flexible resource $N+1$ is Fin.last N. Expectations are Bochner integrals and probabilities are μ.real. The standing assumptions are: $p>0$, $c>0$, $\lambda,\theta\in[0,1]$; demands measurable, almost surely nonnegative and integrable (integrability is needed for expected shortfall and makes every profit integrable); yields measurable, $\{0,1\}$-valued almost surely with $\mathbb P(\tilde Y_j=1)=\theta$, mutually independent, and independent of demand (the paper states the last in Appendix E). The paper's joint density of demand is deliberately not assumed.

The premium $\Delta$ and the indifference cost are not defined as real numbers, because Definition 1's indifference cost need not exist or be unique (for $\theta$ below the threshold both optimal values are $0$ for every $c_{N+1}$ near $c$). "$\Delta\ge 0$" is encoded as "SF is weakly preferred for every $c_{N+1}\le c$", and "$\Delta=0$" as "SF and SD are each weakly preferred to the other at $c_{N+1}=c$". Weak preference $V^{SF,*}\ge V^{SD,*}$ is stated as: every nonnegative SD investment is matched by some nonnegative SF investment; no real supremum is taken. Quantiles $F^{-1}$ in (10) and (12) appear only as parameters with the hypothesis $F(K^*)=$ fractile. Part 3 adds square integrability and positive variances, the conditions under which correlation coefficients exist; the threshold milestone adds almost surely positive demand and $N\ge 1$ for its "if" direction. When $p\le(1-\lambda)c$ the Lean value of the threshold is $\le 0$, so part 2 then covers only $\theta=0$, where it is true.

A formalization that assumed a joint density, took $\Delta$ as a free real satisfying Definition 1, or defined optimal values as real suprema over all of $\mathbb R^N$ would make parts of the goal vacuous or trivial; each is ruled out above.

Needed infrastructure: single-variable newsvendor optimality for general distributions; the Acerbi–Tasche expected shortfall with subadditivity and affine equivariance; the equality case of Cauchy–Schwarz for correlation. The expected-shortfall and correlation lemmas are reusable well beyond this mission, and contributions of them are especially welcome. Out of scope: the loss-averse and CVaR analyses (Propositions 2–3, §3.2–3.3), the perfect-reliability result (Proposition 4, a separate mission), the dual-sourcing networks (§4) and all numerical results.

Selected references

• B. Tomlin and Y. Wang, On the value of mix flexibility and dual sourcing in unreliable newsvendor networks, Manufacturing & Service Operations Management 7(1):37–57, 2005. https://doi.org/10.1287/msom.1040.0063
• C. Acerbi and D. Tasche, On the coherence of expected shortfall, Journal of Banking & Finance 26(7):1487–1503, 2002. https://doi.org/10.1016/S0378-4266(02)00283-2
• C. H. Fine and R. M. Freund, Optimal investment in product-flexible manufacturing capacity, Management Science 36(4):449–466, 1990. https://doi.org/10.1287/mnsc.36.4.449
• J. A. Van Mieghem, Investment strategies for flexible resources, Management Science 44(8):1071–1078, 1998. https://doi.org/10.1287/mnsc.44.8.1071