Operations Research

Prices that respond to inventory

A retailer marking down a seasonal line, an airline raising fares as seats sell, a manufacturer pricing while restocking: each sets prices over time against a finite and changing inventory. Chapter 5 of Talluri and van Ryzin's The Theory and Practice of Revenue Management (2004) collects the structural theory of that problem. Without replenishment, the Bernoulli-arrival model of Gallego and van Ryzin (1994) gives a marginal value of capacity that falls with inventory and with time, hence prices that jump up at each sale and drift down between sales, and the deterministic fluid model bounds it from above. With replenishment, the model of Federgruen and Heching (1999) has a jointly concave and supermodular continuation value, from which the base-stock, posted-price policy follows: below a base-stock level order up to it and post a fixed price, above it order nothing and discount, more the higher the inventory. This mission formalizes those results with Proposition 5.3 as the goal.

Setting

Bernoulli demand (Sect. 5.2.2.2). One customer arrives per period with a random willingness to pay; the firm's decision is the demand rate $d \in [0, 1]$, the probability of a sale at the inverse-demand price $p(t, d)$, with revenue rate $r(t, d) = d\,p(t, d)$ (revenueRate). The value function (5.12) is $V_t(x) = \max_{d}\{r(t, d) - d\,\Delta V_{t+1}(x)\} + V_{t+1}(x)$, $V_{T+1} = 0$, $V_t(0) = 0$ (bernoulliValue), and $\Delta V_t(x) = V_t(x) - V_t(x-1)$ (bernoulliDelta). The deterministic model (5.1) maximizes $\sum_t r(t, d(t))$ over rates with $\sum_t d(t) \le C$ (deterministicValue).

Pricing with replenishment (Sect. 5.3.2). Inventory may be negative (backorders). In period $t$ with inventory $x$ the firm orders up to $y \ge x$ at unit cost $c_t$, chooses a rate $d \in [0, \bar d]$, sells the random demand $D(t, d, \xi_t) = a_t(\xi_t)\,d + b_t(\xi_t)$ (additive, multiplicative or mixed noise), and pays the convex cost $h_t$ on ending inventory. The value function (5.20) is $V_t(x) = \sup_{y \ge x,\, d}\{r(t, d) - c_t(y - x) + G_{t+1}(y, d)\}$ with the continuation value $G_{t+1}(y, d) = \mathbb E[V_{t+1}(y - D(t, d, \xi_t)) - h_t(y - D(t, d, \xi_t))]$ (ReplPricing.value, contValue). Assumption 7.2, marginal revenue decreasing, is the concavity of $r(t, \cdot)$.

Formalization targets

Goal: Proposition 5.3

For every period, $G_{t+1}$ is jointly concave on $\mathbb R \times [0, \bar d]$, $V_t$ is concave on $\mathbb R$, and $G_{t+1}$ has increasing differences in $(y, d)$, the supermodularity that the book states through its partial derivatives: replenishment_concave_supermodular.

Supporting targets

Proposition 5.2, the marginal value of capacity in the Bernoulli model decreases in $t$ and in $x$; the upper bound of Sect. 5.2.2.3, the optimal deterministic revenue dominates the optimal expected stochastic revenue; and the base-stock, posted-price structure of Sect. 5.3.2.1, derived from Proposition 5.3: below the unconstrained optimum $y^0$ order up to it and use $d^0$, above it order nothing and use a rate at least $d^0$ that is nondecreasing in the inventory.

Proposition 5.1 and Lemma 5-5.A.1 (the continuous-demand model without replenishment) are not targets; see the formalization scope. The deterministic sections (efficient prices, discrete price sets), the asymptotic optimality of the deterministic heuristic, the infinite-horizon stationary problem and the multiproduct and finite-population models carry no numbered results.

Significance

Proposition 5.3 is the structural core of joint pricing and inventory control: joint concavity makes the period problem a concave program, and supermodularity is what turns its solution into a policy, the base-stock, posted-price rule that Federgruen and Heching showed optimal and that later work on pricing with inventory builds on. Proposition 5.2 is the reason optimal dynamic prices in the stochastic single-item model rise at every sale and fall while inventory sits, the behaviour of Figure 5.5, and the deterministic upper bound is what justifies the fluid model as a benchmark and a heuristic, the pattern quantified in Table 5.6. None of these has a machine-checked proof; the replenishment result in particular needs the interplay of concavity, expectation and partial maximization on all of $\mathbb R$.

Difficulty

Proposition 5.2 is an induction whose step compares suprema over the rate interval, with the boundary condition $V_t(0) = 0$ breaking the recursion at $x = 1$ and requiring $r(t, 0) = 0$. The deterministic bound is an induction on periods that uses the concavity of the deterministic value in the inventory (a concave program's value) to absorb the two branches of the Bernoulli recursion. The goal needs: integrability and continuity of $V_{t+1}(y - D) - h_t(y - D)$ under bounded noise; that the expectation of a concave function of an affine map is jointly concave, and its increasing differences from those of the concave integrand; that a partial supremum of a jointly concave function over the convex feasible set $\{y \ge x\}$ is concave in $x$; and the boundedness of the objective so that every supremum is a real number. The base-stock item is the segment argument that moves an unconstrained maximizer onto the boundary $y = x$ and a monotone comparative-statics argument on the supermodular objective, with maxima attained by continuity on the compact rate interval.

Formalization scope

Periods are natural numbers with value t the value with $T + 1 - t$ periods to go, the maxima are suprema, and the book's ranges are hypotheses. The demand is affine in the rate, which is the additive and multiplicative models the book names; with a merely convex demand (Assumption 5.1) the joint concavity of Proposition 5.3 fails when $V_{t+1} - h_t$ is not monotone, and the noise has bounded support, strengthening Assumption 7.6. The partial-derivative statements (iii)-(iv) are in difference form. Proposition 5.1 is not formalized: its model (5.11) evaluates $V_{t+1}(x - D)$ at negative inventories the model does not define while truncating revenue at $x$, and its Lemma 5-5.A.1 (joint concavity of $r^+$) is false as stated, its Hessian argument mistaking an indefinite matrix for a negative definite one; a counterexample is in the mission's check. The deterministic model restricts rates to $[0, 1]$, the rates the Bernoulli model can realize.

Selected references

• K. T. Talluri and G. J. van Ryzin, The Theory and Practice of Revenue Management, Kluwer/Springer, 2004, Chapter 5. https://doi.org/10.1007/b139000
• G. Gallego and G. J. van Ryzin, Optimal dynamic pricing of inventories with stochastic demand over finite horizons, Management Science 40(8), 1994. https://doi.org/10.1287/mnsc.40.8.999
• A. Federgruen and A. Heching, Combined pricing and inventory control under uncertainty, Operations Research 47(3), 1999. https://doi.org/10.1287/opre.47.3.454
• W. Elmaghraby and P. Keskinocak, Dynamic pricing in the presence of inventory considerations, Management Science 49(10), 2003. https://doi.org/10.1287/mnsc.49.10.1287.17315
• D. M. Topkis, Supermodularity and Complementarity, Princeton University Press, 1998. https://doi.org/10.1515/9781400822539

When the supplier is the risk

Every model in the earlier chapters of this series treats demand as the uncertain quantity and supply as given. Chapter 9 of Snyder and Shen's Fundamentals of Supply Chain Theory (2019) reverses the roles: demand is deterministic and the supplier fails. A disruption is a binary event, modeled as a two-state Markov process between up and down periods, during which nothing can be ordered. The chapter's thesis, from Snyder and Shen (2006), is that supply uncertainty is a mirror image of demand uncertainty: the optimal base-stock level has the same critical-fractile form as the newsvendor solution but with the fractile taken over the disruption-length distribution (Tomlin 2006), and consolidation, which pools demand risk, now does nothing to expected cost and multiplies its variance, the risk-diversification effect of Schmitt, Sun, Snyder and Shen (2015). The chapter closes with the reliable fixed-charge location problem of Snyder and Daskin (2005). This mission formalizes the chapter's theorems on disruptions, with the risk-diversification theorem as its goal.

Setting

A supplier that is up is disrupted next period with probability $\alpha$; one that is down recovers with probability $\beta$. The disruption chain records $0$ when the supplier is up and $n \ge 1$ in the $n$-th consecutive period of a disruption; its stationary distribution is $\pi_0 = \beta/(\alpha+\beta)$ and $\pi_n = \frac{\alpha\beta}{\alpha+\beta}(1-\beta)^{n-1}$ (disruptionPmf), with distribution function $F(n) = \sum_{i \le n}\pi_i$ (disruptionCdf).

A single location faces demand $d$ per period, pays $h$ per unit held and $p$ per unit backordered per period, and follows a base-stock policy: it orders up to $S$ in every up period and nothing in down periods. In the $n$-th period of a disruption it has $S - (n+1)d$ units on hand or backordered, so its cost is $\hat g(S, n) = h[S-(n+1)d]^+ + p[(n+1)d - S]^+$ (periodCost), and the expected cost per period is $g(S) = \sum_n \pi_n \hat g(S, n)$ (meanCost), with variance $V(S)$ over the disruption state (varCost). The critical fractile $\gamma = p/(p+h)$ and $F^{-1}(\gamma)$, the smallest $n$ with $F(n) \ge \gamma$, determine the optimal level.

In the reliable fixed-charge location problem (RFLP), sites fail independently with probability $q$ and each customer is assigned to a chain of facilities: its level-$r$ facility serves it when the $r$ closer facilities are disrupted, until it is assigned to an emergency facility $u$ that never fails and charges the penalty $\theta_i$. The objective (9.61) is fixed cost plus expected transportation cost, with coefficients $\psi_{ijr} = h_i c_{ij} q^r (1-q)$ (rflpPsi, rflpCost) under the constraints (9.62)-(9.67) (RFLPFeasible).

Formalization targets

Goal: Theorem 9.9

For $N$ identical locations and the centralized location formed by merging them (demand $Nd$):

$$S^*_C = NS^*, \qquad g^*_C = g^*_D = Ng^*, \qquad V^*_C = N V^*_D = N^2 V^*,$$

that is, an optimal single-location level $S$ scales to the optimal centralized level $NS$, the centralized expected cost at $NS$ is $N$ times the single-location cost, and its variance is $N^2$ times the single-location variance. This is risk_diversification.

Supporting targets

Lemma 9.2, the stationary distribution and distribution function of the disruption chain; Lemma 9.4, that the optimal base-stock level is a multiple of $d$; Theorem 9.5, $S^* = d + dF^{-1}(p/(p+h))$, as the least minimizer of $g$; and Theorem 9.10, that in every optimal RFLP solution consecutive backup assignments are ordered by cost. Theorem 9.3, the optimality of base-stock policies, is cited by the book to Song and Zipkin without a model of the policy space and is not a target; Proposition 9.1 and the multisupplier results of Sect. 9.4 are left for a later mission, as discussed below.

Significance

Theorem 9.5 is the supply-side newsvendor formula: it says exactly how much inventory buys protection against disruptions of a given length, and it underlies the disruption models used in practice for raw-material buffers. Theorem 9.9 is the chapter's central insight and the reason supply and demand uncertainty call for opposite strategies: pooling reduces expected cost under demand uncertainty but only redistributes risk under supply uncertainty, concentrating it. Its three identities are what a risk-averse planner needs to compare the two designs by a mean-variance criterion. Theorem 9.10 is what lets the RFLP be formulated without ordering constraints and solved by Lagrangian relaxation like the UFLP.

None of these results has a machine-checked proof. The book proves Theorem 9.5 and the identities behind Theorem 9.9, sketches Lemma 9.4, and leaves Lemma 9.2 and Theorem 9.10 as exercises. The formal treatment of the piecewise-linear cost $g$ and its finite differences is reusable for the yield-uncertainty and multi-supplier models of the same chapter.

Difficulty

The cost $g$ is an infinite series whose terms grow linearly in $n$ against a geometric weight, so every statement about it begins with summability, and the finite-difference identity $\Delta g(S) = d[(h+p)F(S/d - 1) - p]$ requires exchanging a difference with a sum. Theorem 9.5 then needs the convexity and piecewise linearity of $g$ to pass from a sign condition on slopes at multiples of $d$ to a global minimum over all real $S$, and the identification of the least minimizer needs the slopes to be strictly negative below $S^*$. The obvious idea, treating the problem as a discrete newsvendor over multiples of $d$, is only half of the argument: it does not by itself exclude non-multiple minimizers, which is what Lemma 9.4 asserts.

Lemma 9.2 is elementary but the stationary equations involve a series over all down states, and the proof must establish summability before manipulating it. Theorem 9.9's scaling identities are termwise, but the optimality transfer in part 1 requires the scaling to preserve minimizers, which follows from the cost identity holding for every $S$.

Theorem 9.10 is an exchange argument on a binary program with layered constraints. The delicate case is the emergency facility: swapping it into a lower level is infeasible, and the correct move is to promote it and drop the later assignment, which changes the constraints for every higher level; the argument must show feasibility of the modified solution level by level.

Formalization scope

The disruption distribution is given by Lemma 9.2's formula rather than defined as the stationary distribution, and Lemma 9.2 shows it satisfies the stationary equations; the theorems assume $0 < \alpha \le 1$ and $0 < \beta \le 1$, under which every series is a geometric series times a polynomial and is summable. The quantity $F^{-1}(\gamma)$ enters Theorem 9.5 as a natural number $k$ characterized by $F(k) \ge \gamma$ and $F(n) < \gamma$ for $n < k$, which exists since $F(n) \to 1 > \gamma$; the conclusion asserts both optimality and leastness of $d + dk$ among all real levels.

Theorem 9.9 is stated as the scaling of the single-location functions; the decentralized totals $Ng^*$ and $NV^*$ are the mean and variance of a sum of $N$ independent copies, which the book asserts rather than derives, and are not modeled separately. In the RFLP, levels are indexed by Fin m, the emergency facility is a designated index $u$ whose data satisfy the book's conventions through the hypotheses, and demands are positive with $0 < q < 1$, both needed: with $q = 0$ or $h_i = 0$ backup assignments are free and any order is optimal.

The EOQ with disruptions (Proposition 9.1) is a renewal-reward derivation without a formal model of the renewal process in the book, and the multisupplier newsvendor of Sect. 9.4 (Lemma 9.6, Theorems 9.7 and 9.8) rests on differentiability conditions the book defers to Dada et al. and on a lemma it leaves as an exercise; both are natural extensions on the same definitions rather than targets here.

Selected references

• L. V. Snyder and Z.-J. M. Shen, Fundamentals of Supply Chain Theory, 2nd ed., Wiley, 2019, Chapter 9. https://doi.org/10.1002/9781119584445
• B. Tomlin, On the value of mitigation and contingency strategies for managing supply chain disruption risks, Management Science 52(5), 2006. https://doi.org/10.1287/mnsc.1060.0515
• A. J. Schmitt, S. A. Sun, L. V. Snyder and Z.-J. M. Shen, Centralization versus decentralization: risk pooling, risk diversification, and supply chain disruptions, Omega 52, 2015. https://doi.org/10.1016/j.omega.2014.10.010
• L. V. Snyder and M. S. Daskin, Reliability models for facility location: the expected failure cost case, Transportation Science 39(3), 2005. https://doi.org/10.1287/trsc.1040.0107
• L. V. Snyder and Z.-J. M. Shen, Supply and demand uncertainty in multi-echelon supply chains, working paper, 2006. https://doi.org/10.1287/msom.1080.0224

Where to put the warehouses

Choosing where to open distribution centers is the strategic decision that fixes a supply chain's shape for years. The basic model, the uncapacitated fixed-charge location problem (UFLP) of Balinski (1965), trades the fixed cost of opening sites against the cost of transporting demand from open sites to customers. It is NP-hard, yet routinely solved to optimality, and the reason is a fact about its relaxations: the LP relaxation is unusually tight, and Lagrangian relaxation, which Cornuejols, Fisher and Nemhauser (1977) brought to location problems, gives the same bound with a subproblem solvable by inspection. Chapter 8 of Snyder and Shen's Fundamentals of Supply Chain Theory (2019) develops the UFLP, its Lagrangian relaxation and Erlenkotter's (1978) DUALOC dual-ascent method, then the p-median problem with Hakimi's (1965) node-optimality theorem and the covering models. This mission formalizes the chapter's numbered results, with the equality of the Lagrangian and LP bounds as its goal.

Setting

Customers $i \in I$ have demands $h_i$; candidate sites $j \in J$ have fixed costs $f_j$; shipping one unit from $j$ to $i$ costs $c_{ij}$. A solution opens sites ($x_j \in \{0,1\}$) and assigns demand fractions ($y_{ij} \ge 0$, $\sum_j y_{ij} = 1$, $y_{ij} \le x_j$); its cost is $\sum_j f_j x_j + \sum_i \sum_j h_i c_{ij} y_{ij}$ (uflpCost, UFLPFeasible). The optimal value is $z^*$ (uflpOpt); relaxing $x_j \in \{0,1\}$ to $0 \le x_j \le 1$ gives the LP relaxation with value $z_{LP}$ (uflpLP).

Lagrangian relaxation removes the assignment constraints and charges $\lambda_i$ per unit of violation. For fixed multipliers $\lambda$ the subproblem (UFLP-LR$_\lambda$) minimizes $\sum_j f_j x_j + \sum_i\sum_j (h_i c_{ij} - \lambda_i) y_{ij} + \sum_i \lambda_i$ over $y_{ij} \le x_j$, $x$ binary, $y \ge 0$ (lagrObjective, LagrFeasible), with value $z_{LR}(\lambda)$ (zLR). It separates by site: the benefit of opening $j$ is $\beta_j = \sum_i \min\{0, h_i c_{ij} - \lambda_i\}$ (benefit), and $j$ is opened iff $\beta_j + f_j < 0$. The best bound is the Lagrangian dual value $z_{LR} = \max_\lambda z_{LR}(\lambda)$ (zLRbest).

DUALOC works with the condensed dual of the LP relaxation, whose variables $v_i$ satisfy $\sum_i \max\{0, v_i - \hat c_{ij}\} \le f_j$ with $\hat c_{ij} = h_i c_{ij}$. A dual solution $v$ and a site set $J^+$ form a primal-dual pair (PDP) when these constraints are tight on $J^+$ and every customer has a site in $J^+$ with $\hat c_{ij} \le v_i$; the primal solution opens $J^+$ and assigns each customer to its nearest open site $j^+(i)$ (NearestIn, primalX, primalY).

For the p-median problem on a network, the customers are the nodes, $d$ is the shortest-path distance between nodes, and a facility may sit at position $t$ along an edge $(u, w)$ of length $\ell$, at distance $\min\{d(i,u) + t\ell, d(i,w) + (1-t)\ell\}$ from node $i$ (NetPoint, netDist). The p-center problem minimizes the largest distance from a customer to its nearest of $p$ open sites; pCenterValue c p is its optimal value.

Formalization targets

Goal: Corollary 8.2

For every instance with at least one candidate site,

$$z_{LP} \;=\; z_{LR} \;=\; \sup_\lambda z_{LR}(\lambda).$$

This is lagrangian_equals_lp.

Supporting targets

Theorem 8.1, the closed form $z_{LR}(\lambda) = \sum_j \min\{0, \beta_j + f_j\} + \sum_i \lambda_i$ with its optimal solution; the bounds (8.16) $z_{LR}(\lambda) \le z^*$ and (8.19) $z_{LP} \le z_{LR} \le z^*$; Theorem 8.3, the variable-fixing tests; Lemma 8.4, the DUALOC duality gap $z^+_P - z^+_D = \sum_i \sum_{j \in J^+, j \ne j^+(i)} \max\{0, v_i - \hat c_{ij}\}$; Lemma 8.6, the characterization of complementary slackness violations; Theorem 8.7, Hakimi's theorem that some $p$ nodes are optimal among all $p$-point sets; Lemma 8.8, the equivalence between the $p$-center value being at most $r$ and a set cover of radius $r$ with at most $p$ sites. Proposition 8.5, which concerns the output of a specific procedure, is not a target.

Significance

Corollary 8.2 explains the behavior of every Lagrangian location code: the bound cannot beat the LP bound, so its value lies in the ease of the subproblem and in extensions to nonlinear location models (the location model with risk pooling of Chapter 12) where no LP is available. Theorem 8.1 is the subproblem solution those codes use; Theorem 8.3 is the variable-fixing device of Daskin, Snyder and others that shrinks branch-and-bound trees. Lemmas 8.4 and 8.6 are the analytical core of DUALOC, the method that made large UFLP instances solvable in the 1970s. Hakimi's theorem is the reason the $p$-median problem is a discrete problem at all, and Lemma 8.8 is the reason $p$-center problems are solved by bisection over covering problems rather than by their weak MIP formulation.

None of these results has a machine-checked proof. The book proves Theorems 8.1 and 8.3 and Lemma 8.6, cites Corollary 8.2 to Appendix D and Theorem 8.7 to Hakimi, and leaves Lemmas 8.4 and 8.8 as exercises. The formal treatment of the integrality property and of Lagrangian duality for a linear objective over a product of boxes is reusable for the p-median and capacitated variants the chapter goes on to discuss.

Difficulty

The goal is an LP duality statement in disguise, and the obvious idea, that $z_{LR}(\lambda)$ is the dual function of the LP relaxation, is exactly what needs proof. Two facts must be established: that for fixed $\lambda$ the subproblem over binary $x$ has the same value as over $x \in [0,1]$, because after the optimal $y$ is substituted the objective is linear in $x$; and that the supremum over $\lambda$ of the resulting concave piecewise-linear function equals the LP minimum. The second is strong duality for a linear program, which Mathlib does not provide ready-made; it has to be obtained either through a Farkas-type argument or by exhibiting, for the LP optimum, a multiplier vector that attains it, which for this problem can be read off the LP dual. The book proves none of this; it invokes Lemma D.3.

The bounds (8.16) and (8.19) are easier but not free: the infima and suprema defining $z^*$, $z_{LP}$ and $z_{LR}$ must be shown attained, which needs finiteness of the binary choices and compactness of the assignment polytope. Theorem 8.3 depends on the value of the subproblem with one variable forced, which is Theorem 8.1 applied to a modified instance. Hakimi's theorem needs a concavity argument in each point's position and a bookkeeping step, since moving several points to nodes may merge them and the result must still have exactly $p$ nodes. Lemma 8.8 is combinatorial and short once the $p$-center value is identified with a minimum over $p$-subsets.

Formalization scope

Customers and sites are Fin n and Fin m; demands, costs and fixed costs are arbitrary reals, as the book's formulations are, and the theorems that need it assume $m \ge 1$. Optimal values are infima or suprema of the sets of attainable objective values, all of which are nonempty and bounded under the stated hypotheses. The Lagrangian dual value is a supremum over all real multiplier vectors, so Corollary 8.2 asserts in particular that the supremum equals the attained LP value.

The DUALOC statements take the nearest-facility assignment $j^+(i)$ as a function a with the defining property, so ties are resolved by the hypothesis, and the complementary slackness violation is written exactly as (8.51) with $(x^+, y^+)$ substituted. Hakimi's theorem is stated for a family of $p$ points with repetition allowed, which is stronger than for a set. It assumes what the book's network supplies: the node distances satisfy the triangle inequality, since they are shortest-path distances, and every edge carrying a point is at least as long as the distance between its endpoints. The argument needs both: they make the ends of an edge coincide with its nodes, and without them a point on a short fictitious edge can beat every node. The set covering value in Lemma 8.8 is expressed through the existence of a cover with at most $p$ sites rather than as a natural-number infimum, whose value $0$ on infeasible instances would falsify the equivalence.

The definition module is shared by all ten items. The Lagrangian relaxation of the $p$-median problem (Sect. 8.3.2.2), the continuous knapsack subproblem of the capacitated problem, and Proposition 8.5 on the dual-ascent procedure are natural extensions on the same definitions.

Selected references

• L. V. Snyder and Z.-J. M. Shen, Fundamentals of Supply Chain Theory, 2nd ed., Wiley, 2019, Chapter 8. https://doi.org/10.1002/9781119584445
• M. L. Balinski, Integer programming: methods, uses, computation, Management Science 12(3), 1965. https://doi.org/10.1287/mnsc.12.3.253
• G. Cornuejols, M. L. Fisher and G. L. Nemhauser, Location of bank accounts to optimize float, Management Science 23(8), 1977. https://doi.org/10.1287/mnsc.23.8.789
• D. Erlenkotter, A dual-based procedure for uncapacitated facility location, Operations Research 26(6), 1978. https://doi.org/10.1287/opre.26.6.992
• S. L. Hakimi, Optimum distribution of switching centers in a communication network and some related graph theoretic problems, Operations Research 13(3), 1965. https://doi.org/10.1287/opre.13.3.462
• A. M. Geoffrion, Lagrangean relaxation for integer programming, Mathematical Programming Study 2, 1974. https://doi.org/10.1007/BFb0120690

Why the newsvendor orders too little

A retailer facing uncertain single-period demand and buying from a supplier at a wholesale price orders less than the two of them together would want. The reason is not irrationality but incentives: the retailer bears the whole cost of unsold stock while the supplier collects a margin on every unit ordered, so each party marks up its own cost and the combined markup, Spengler's (1950) double marginalization, depresses the order. Pasternack (1985) showed that a buyback credit for unsold units, priced correctly, realigns the retailer with the chain, and Cachon (2003) surveys the contracts that followed. Chapter 14 of Snyder and Shen's Fundamentals of Supply Chain Theory (2019) develops this as a Stackelberg game on the newsvendor model: the supplier sets contract terms, the retailer sets the order quantity. This mission formalizes the chapter's seven theorems, with the buyback allocation theorem, which shows that buyback both coordinates the chain and can divide its profit in any proportion, as the goal.

Setting

Demand $D$ is a random variable with law on $\mathbb{R}$ and mean $\mu$. The retail price is $r$; the supplier's and retailer's per-unit costs are $c_s$ and $c_r$ with $c = c_s + c_r < r$; lost sales cost the two parties goodwill penalties $p_s$ and $p_r$ with $p = p_s + p_r$; unsold units salvage for $v < c_r$ (ContractData). With $S(Q) = \mathbb{E}[\min\{Q, D\}]$ the expected sales (expSales) and $I(Q) = Q - S(Q)$ the expected leftover (expLeftover), a transfer payment $T(Q)$ from retailer to supplier determines the two profits (retailerProfit, supplierProfit),

$$\pi_r(Q) = (r - v + p_r)S(Q) - (c_r - v)Q - p_r\mu - T(Q), \qquad \pi_s(Q) = p_s S(Q) - c_s Q - p_s\mu + T(Q),$$

whose sum $\Pi(Q) = (r - v + p)S(Q) - (c - v)Q - p\mu$ (chainProfit) is independent of the contract. The chain-optimal quantity $Q_0$ maximizes $\Pi$; the retailer's and supplier's optimal quantities $Q^*_r$, $Q^*_s$ maximize their own profits. A contract coordinates the chain when $Q^*_r = Q^*_s = Q_0$, stated here as equality of the sets of maximizers, and is a coordinating contract type when some choice of its parameters does this with both profits positive.

The four contracts are their transfer payments. Wholesale price: $T = wQ$. Buyback: $T = wQ - b\,I(Q)$, the supplier crediting $b$ per unsold unit, with $0 \le b \le r - v + p_r$ and $w = w(b)$ of (14.22). Revenue sharing: the retailer keeps a fraction $\phi$ of sales and salvage revenue, $T = (w + (1-\phi)v)Q + (1-\phi)(r - v)S(Q)$, with $w = w(\phi)$ of (14.34). Quantity flexibility: the supplier reimburses the retailer's loss $w + c_r - v$ on unsold units up to $\delta Q$, $T = wQ - (w + c_r - v)\int_{(1-\delta)Q}^{Q} F(t)\,dt$, with $w = w(\delta)$ of (14.46). For buyback, $\lambda = (r - v + p_r - b)/(r - v + p)$ is the retailer's share of the chain profit (buybackShare), and $b_1 < b_2$ (buybackB1, buybackB2) are the credits at which one party earns everything.

Formalization targets

Goal: Theorem 14.5

Under buyback with $w(b)$ at the chain-optimal $Q_0$, the retailer's profit is decreasing and the supplier's increasing in $b \in [0, r - v + p_r]$, with $0 < b_1 < b_2 < r - v + p_r$ and

$$\pi_r(Q_0, w(b_1), b_1) = \Pi(Q_0), \qquad \pi_s(Q_0, w(b_2), b_2) = \Pi(Q_0),$$

the supplier losing money for $b < b_1$, both earning positive profit for $b_1 < b < b_2$, and the retailer losing money for $b > b_2$. This is buyback_allocation.

Supporting targets

Equation (14.8), $Q_0$ maximizes $\Pi$ iff $\bar F(Q_0) = (c - v)/(r - v + p)$; Theorem 14.1, the wholesale price contract coordinates iff $w = c_s - \frac{c-v}{r-v+p}p_s$, at which the supplier's profit is negative; Theorem 14.2, $Q^*_r < Q_0$ whenever $w > c_s$; Theorem 14.3, for IGFR demand the supplier's induced profit $\pi_s(Q, w(Q))$ is unimodal; the identities (14.27) and (14.28), $\pi_r = \lambda\Pi + \mu(\lambda p - p_r)$ and its complement under buyback; Theorem 14.4, buyback with $w(b)$ coordinates; Theorem 14.6, revenue sharing with $w(\phi)$ coordinates; Theorem 14.7, quantity flexibility with $w(\delta)$ makes $Q_0$ optimal for the retailer.

Significance

The chapter's theorems are the analytical basis of contract design in newsvendor supply chains. Theorem 14.1 and 14.2 make double marginalization precise: coordination by price alone is possible only at a price the supplier rejects, and any acceptable price makes the retailer under-order. Theorem 14.3 is what lets the supplier optimize the wholesale price at all, and is the reason the IGFR class of Lariviere and Porteus (2001) is standard in the field. Theorems 14.4 to 14.6 show that buyback and revenue sharing coordinate and, through the share $\lambda$, that the chain profit can be split arbitrarily, so a coordinating contract can be made acceptable to both parties. Theorem 14.7 shows the limits: quantity flexibility coordinates the retailer but not necessarily the supplier.

None of these results has a machine-checked proof. The book proves Theorems 14.1, 14.3, 14.4, 14.5, 14.6 and 14.7 and leaves 14.2 as an exercise. The formalization of the fractile characterization and of the affine profit identities is reusable for the many contract types (sales rebates, quantity discounts) the chapter cites but does not analyze.

Difficulty

The wholesale price results are first-order conditions on concave functions, and the difficulty is entirely in the analysis: $S(Q) = \mathbb{E}[\min\{Q, D\}]$ has derivative $\bar F(Q)$ for every $Q$ when $F$ is continuous, which is a differentiation under the integral that has to be carried out for a Lipschitz integrand and an arbitrary law, and the maximizers of the concave profit must then be identified with the solutions of the fractile equation, including existence by the intermediate value theorem. Theorem 14.1's "only if" direction requires that a coincidence of maximizer sets pins the fractile and hence the price, which is where strict monotonicity of $F$ enters.

Theorem 14.3 is the delicate one. The obvious approach, concavity of $\pi_s(Q, w(Q))$, fails: the book stresses the function is not concave in general. The proof is a sign-change argument on the derivative (14.16), which is $\bar F(Q)$ times a bracket that IGFR makes decreasing, minus a constant; one must show the derivative is positive near $0$, eventually negative, and crosses zero exactly once, and that the last needs both $\bar F$ strictly decreasing and the bracket positive at the crossing. Working with a density in Mathlib means relating the withDensity law to the distribution function throughout.

The buyback, revenue sharing and quantity flexibility theorems are algebra once the right identity is found: $\pi_r$ is an affine function of $\Pi$ with slope $\lambda$. The formalization must handle the boundary cases the book glosses over, where $\lambda = 0$ or $\lambda = 1$ and one party is indifferent among all quantities, so "the same $Q$ maximizes" holds only in one direction. Theorem 14.5 also needs $\Pi(Q_0) \le \mu(r - c)$, a Jensen-type bound $S(Q) \le \min\{Q, \mu\}$, for $b_1 > 0$, and the ordering $b_1 < b_2$ needs $\Pi(Q_0) > 0$, which the book's proof does not isolate.

Formalization scope

Demand is an arbitrary probability law on $\mathbb{R}$ with finite mean, not assumed nonnegative; the book's own examples use normal demand. Optimal quantities are maximizers over all of $\mathbb{R}$ (IsMaxOn … Set.univ), and coordination is the coincidence of maximizer sets, with the degenerate endpoints of the parameter ranges stated as one-directional. Where the book uses a density, continuity of the distribution function (NullSingletonClass) is assumed instead, except in Theorem 14.3, where the density $f$ is explicit, continuous on $[0, \infty)$ (so the exponential law is included), positive on $(0, \infty)$, and IGFR on $(0, \infty)$. Strict monotonicity of $F$ on $\mathbb{R}$ is never assumed, since it would rule out every nonnegative demand law. Theorem 14.1 assumes $p_s > 0$ and a positive chain optimum, $\bar F(0) > (c - v)/(r - v + p)$, both implicit in the book's proof.

The transfer payments are functions of $Q$ and the profits are defined for every $Q$, so the theorems compare values of one family of functions; the book's $\bar F$ is $1 - F$ with Mathlib's cdf, and the quantity flexibility integral is an interval integral. Theorem 14.5 takes $\Pi(Q_0) > 0$, $\mu > 0$ and $p_s, p_r > 0$ as hypotheses. Without positive goodwill costs its strict inequalities $0 < b_1$ and $b_2 < r - v + p_r$ fail (at $p_s = 0$, $b_1 = 0$; at $p_r = 0$, $b_2 = r - v + p_r$).

The definition module is shared by all eleven items. The equivalence (14.42)-(14.43) of revenue sharing and buyback, the supplier's stationarity under quantity flexibility (Problem 14.11) and the allocation results for revenue sharing (14.40)-(14.41) are natural extensions on the same definitions.

Selected references

• L. V. Snyder and Z.-J. M. Shen, Fundamentals of Supply Chain Theory, 2nd ed., Wiley, 2019, Chapter 14. https://doi.org/10.1002/9781119584445
• B. A. Pasternack, Optimal pricing and return policies for perishable commodities, Marketing Science 4(2), 1985. https://doi.org/10.1287/mksc.4.2.166
• G. P. Cachon, Supply chain coordination with contracts, in Handbooks in Operations Research and Management Science 11, 2003. https://doi.org/10.1016/S0927-0507(03)11006-7
• M. A. Lariviere and E. L. Porteus, Selling to the newsvendor: an analysis of price-only contracts, Manufacturing & Service Operations Management 3(4), 2001. https://doi.org/10.1287/msom.3.4.293.9971
• G. P. Cachon and M. A. Lariviere, Supply chain coordination with revenue-sharing contracts, Management Science 51(1), 2005. https://doi.org/10.1287/mnsc.1040.0215
• J. J. Spengler, Vertical integration and antitrust policy, Journal of Political Economy 58(4), 1950. https://doi.org/10.1086/256964

Batch quantities that cannot be chosen one site at a time

Chapter 9 of Axsäter's Inventory Control opens with the observation that in a multi-echelon system it is not optimal to choose batch quantities installation by installation: the batch at one site is the demand pattern of the next site upstream. Even with constant customer demand the exact optimum can be complicated, and the book's Example 9.4 shows a four-stage serial system whose optimal batch at one stage alternates between two values over time. Roundy (1985, 1986) showed that this complexity can be avoided at a guaranteed price: restrict every batch quantity to be a power of two times a common basic quantity, nested from stage to stage, and the best such policy costs at most 2 % more than the optimum. The book presents the result for a serial system and remarks that the same approach handles assembly and distribution systems and, in Sect. 7.3.1.2, joint replenishments. It is the capstone of Chapter 9 and the multi-echelon payoff of the powers-of-two analysis of Chapter 7.

Setting

A serial system has $N$ installations; installation $i$ produces item $i$ from one unit of item $i+1$, item $N$ is obtained from an outside supplier, and item 1 faces a constant, continuous final demand $d$. Lead-times are zero, shortages are not allowed, production is instantaneous, and each batch quantity $Q_i$ is constant over time. Installation $i$ has an ordering cost $A_i$ per batch and an echelon holding cost $e_i$ per unit and time unit, charged on the echelon stock (the stock at installation $i$ and everything downstream), so that the cost per time unit is the sum of $N$ single-item costs of the chapter 4 form,

$$C(Q) \;=\; \sum_{i=1}^{N}\Big(e_i\frac{Q_i}{2} + A_i\frac{d}{Q_i}\Big) \qquad\text{(Eq. 9.17).}$$

The book first works out the two-level case, where the optimum has $Q_2 = kQ_1$ for a positive integer $k$, the cost (9.9) is the EOQ cost with modified parameters $A_1 + A_2/k$ and $e_1 + ke_2$, and the best $k$ is found from $k^{*} = \sqrt{A_2e_1/(A_1e_2)}$ by a rounding rule.

For $N$ stages, Roundy's constraints (9.16) require $Q_i = 2^{k_i}Q_{i-1}$ with nonnegative integers $k_i$, so that every solution is nested. The relaxed constraints (9.18) require only $Q_{i-1} \le Q_i$; they are implied by (9.16), the relaxed problem is convex with linear constraints, and its solution $Q^{\mathrm{rel}}$ is computed by aggregating consecutive stages whose cost ratios $A_i/e_i$ decrease. Roundy's solution rounds $Q^{\mathrm{rel}}$ to $Q_i = 2^{m_i}q$ for a basic quantity $q$, chosen as in Proposition 7.2.

Formalization targets

Goal — Roundy's 98 % approximation

For $d > 0$, $A_i > 0$, $e_i > 0$ and any minimizer $Q^{\mathrm{rel}}$ of $C$ over positive batch quantities satisfying (9.18), there exist $q > 0$ and integers $m_1 \le \dots \le m_N$ such that $Q_i = 2^{m_i}q$ satisfies (9.16) and

$$C\big(2^{m}q\big) \;\le\; \frac{1}{\sqrt 2\,\ln 2}\,C\big(Q^{\mathrm{rel}}\big).$$

Supporting targets

The two-level results of Sect. 9.2.1: the equivalence of the installation and echelon cost forms (9.6) and (9.9); the optimal $Q_1$ and cost (9.10)-(9.11) for a given $k$; the closed form and convexity of $C(k)^2$ (9.12) and the real minimizer $k^{*}$ (9.13); and the integer rounding rule with its corollary that $A_1/e_1 \ge A_2/e_2$ forces $k = 1$. For $N$ stages: existence of the relaxed optimum; the aggregation lemma, that $A_i/e_i < A_{i-1}/e_{i-1}$ forces $Q^{\mathrm{rel}}_i = Q^{\mathrm{rel}}_{i-1}$; that (9.16) implies (9.18), so the relaxed optimum bounds every powers-of-two policy from below; and that rounding to the nearest power of two times $q$ is monotone and lands within a factor $\sqrt 2$.

Significance

The result itself. Roundy's theorem replaces an intractable lot-sizing problem by a closed-form computation with a provable 2 % guarantee, and the policies it produces are the nested, periodic schedules that production planning wants anyway. In Example 9.4 the rounding with $q = 1$ is already within 0.7 % of the relaxed bound. The two-level analysis has its own use: the modified parameters $A_1 + A_2/k$ and $e_1 + ke_2$ are what the Blackburn-Millen heuristic of Sect. 9.3.2 feeds to the Wagner-Whitin algorithm under time-varying demand, and the condition $A_1/e_1 \ge A_2/e_2$ tells when a two-stage system collapses to one stage.

Formalizing it. The book proves the bound in a paragraph that leans on three earlier results: Proposition 7.2 for the rounding, the Lagrangean relaxation for the lower bound, and the aggregation algorithm for the structure of $Q^{\mathrm{rel}}$. Formalizing it makes explicit what the paragraph glosses: that the multipliers vanish off tight constraints, that equal quantities round to equal quantities, and that the comparison class is the class of nested constant-batch policies. The published Proposition 7.2 (pot_two_percent) and the mean value $1/(\sqrt 2\ln 2)$ are cited as reference items. Nothing here is open; no statement has a machine-checked proof yet.

Difficulty

The obvious argument, rounding $Q^{\mathrm{rel}}$ item by item and invoking Proposition 7.2 for each, does not work: Proposition 7.2 bounds the rounded cost relative to each item's unconstrained optimum, and $Q^{\mathrm{rel}}_i$ is generally not that optimum. The proof must pass through the Lagrangean relaxation (9.19)-(9.20), under which $Q^{\mathrm{rel}}$ is the unconstrained optimum for the modified holding costs $e_i' = e_i - 2\lambda_i + 2\lambda_{i+1}$, apply Proposition 7.2 there, and transfer the bound back using complementary slackness: the multiplier $\lambda_i$ is positive only where $Q^{\mathrm{rel}}_i = Q^{\mathrm{rel}}_{i-1}$, and equal quantities round to equal quantities, so the correction terms $\lambda_i(Q_i - Q_{i-1})$ vanish for both $Q^{\mathrm{rel}}$ and its rounding. A solver therefore needs the KKT conditions for this convex program, or an equivalent direct argument through the aggregation structure (within an aggregate all quantities are equal and their sum is an EOQ problem). The two-level statements and the rounding lemma are elementary.

Formalization scope

Stages are indexed by Fin N; the cost is serialCost A e d Q = ∑ i, eoqCost (A i) d (e i) (Q i) with eoqCost imported from the chapter 4 definitions, and the two-level cost is eoqCost (A1 + A2/k) d (e1 + k e2) Q1 by definition, so the published eoq_optimal and eoq_cost_at_eoq apply to it directly. SerialNested and SerialPowerOfTwo are the constraints (9.18) and (9.16) on consecutive indices; for $N \le 1$ both hold vacuously and the goal is Proposition 7.2 for one item. potRound q Q is $\lfloor \log_2(Q/q) + \tfrac12\rfloor$.

All theorems assume $d, A_i, e_i > 0$ and positive batch quantities. The book says "nonnegative ordering and echelon holding costs"; strict positivity is needed for the relaxed problem to have a solution at all ($e_i = 0$ or $A_i = 0$ sends the optimal $Q_i$ to $\infty$ or $0$), and it is what the book's own examples satisfy. The relaxed optimum enters the goal as a hypothesis, with existence stated separately; uniqueness is not used. The constant is the exact $1/(\sqrt 2\ln 2)$.

Two readings are excluded. The bound is not against an arbitrary nested $Q$, for which it would be false, but against the relaxed optimum; and the comparison class is stated as nested constant-batch policies, the class the relaxed problem bounds directly, not the book's larger class of time-varying policies, which would need a dynamic model. The definitions are reusable for assembly systems and for the joint replenishment problem of Sect. 7.3.1.2, whose Roundy analysis is the same with a fictive item 0 of zero holding cost; contributions in that direction are welcome.

Selected references

• Sven Axsäter, Inventory Control, 3rd edition, International Series in Operations Research & Management Science 225, Springer, 2015, Sect. 9.2. DOI 10.1007/978-3-319-15729-0
• Robin Roundy, 98%-Effective Integer-Ratio Lot-Sizing for One-Warehouse Multi-Retailer Systems, Management Science 31(11), 1985, pp. 1416-1430. DOI 10.1287/mnsc.31.11.1416
• Robin Roundy, A 98%-Effective Lot-Sizing Rule for a Multi-Product, Multi-Stage Production/Inventory System, Mathematics of Operations Research 11(4), 1986, pp. 699-727. DOI 10.1287/moor.11.4.699
• John A. Muckstadt and Robin O. Roundy, Analysis of Multistage Production Systems, in: Handbooks in Operations Research and Management Science 4, Elsevier, 1993, pp. 59-131. DOI 10.1016/S0927-0507(05)80182-4
• Peter L. Jackson, William L. Maxwell and John A. Muckstadt, The Joint Replenishment Problem with a Powers-of-Two Restriction, IIE Transactions 17(1), 1985, pp. 25-32. DOI 10.1080/07408178508975268

Why the policy class is not up for debate

Every model in Chapters 5 and 6 of Axsäter's Inventory Control assumes at the outset that the ordering policy is of $(R,Q)$ or $(s,S)$ type. Section 6.2 asks whether better policies exist and answers, for the case in which there are no ordering costs but every order must be a multiple of a fixed batch quantity $Q$, that none do: Proposition 6.1, "an $(R,Q)$ policy is optimal", with a proof the book attributes to Chen (2000). For $Q = 1$ it is the optimality of an order-up-to-$S$ policy in the absence of ordering costs, and for continuous or Poisson demand it transfers to $(s,S)$ policies, which are then the same thing. The proposition is the one place in the book where a policy is compared against every feasible alternative rather than against other members of its own family, and its proof is short enough to be given in full, which makes it the natural capstone of Chapter 6.

Setting

Demand is compound Poisson: customers arrive according to a Poisson process with rate $\lambda$ and each demands an integral number of units, with sizes $D_0, D_1, \dots$ independent and identically distributed with law $f$ on the positive integers, independent of the arrival process. The book's standing assumption that not all demands are multiples of some integer larger than one is kept. Writing $T_n$ for the $n$-th arrival time, $N(t)$ for the number of arrivals by time $t$ and $S_n = D_0 + \dots + D_{n-1}$, the total demand by time $t$ is $S_{N(t)}$.

The replenishment lead-time $L$ is constant and $D(L)$, the demand over a lead-time, has law $D$. A holding cost $h > 0$ and a shortage cost $b_1 > 0$ per unit and time unit are charged. There are no ordering costs, but all orders must be multiples of a given batch quantity $Q \ge 1$ and can only be triggered by customer demands. A policy is therefore any rule $m$ that decides at each demand epoch how many batches to order; with initial position $y_0$ the inventory position evolves as $y_{n+1} = y_n - D_n + m_nQ$ (Eq. 6.22), and $y_t = y_{N(t)}$.

The standard argument of Sect. 5.3.2 gives the cost rate at time $t + L$ as

$$g(y_t), \qquad g(k) = -b_1(k - \mu') + (h+b_1)\sum_{j=1}^{k} j\,\Pr[D(L) = k - j],$$

the expected holding-plus-shortage cost rate of an inventory level $k - D(L)$ (Eq. 6.20), which is convex in $k$ with $g(k) \to \infty$ as $|k| \to \infty$. The band cost is $\bar g(y) = \sum_{j=1}^{Q} g(y+j)$ and $R$ denotes an integer minimizing $\bar g$. The $(R,Q)$ policy orders, as soon as the position is at or below $R$, the smallest number of batches that brings it above $R$; its position lives in the band $\{R+1, \dots, R+Q\}$ from the first order on. The performance measure is the long-run average cost rate $\frac{1}{T}\int_0^T g(y_{t-L})\,\mathrm{d}t$ as $T \to \infty$.

Formalization targets

Goal — Proposition 6.1

Almost surely, (1) for every policy $m$ and every $y_0$,

$$\liminf_{T\to\infty} \frac{1}{T}\int_0^T g\big(y^{m}_{t-L}\big)\,\mathrm{d}t \;\ge\; \frac{\bar g(R)}{Q},$$

and (2) the $(R,Q)$ policy attains it:

$$\frac{1}{T}\int_0^T g\big(y^{(R,Q)}_{t-L}\big)\,\mathrm{d}t \;\longrightarrow\; \frac{\bar g(R)}{Q}.$$

Supporting targets

Lemma 6.1, that $x \mapsto g(z + xQ)$ is convex and minimized at the representative of $z$ in the band; the closed form of the $(R,Q)$ position, $y_0 - S_n$ until the first order and the band representative of $y_0 - S_n$ afterwards; the uniform occupation of the band by the reduced process $y_t'$, the book's "the steady state distribution can be shown to be uniform", and its consequence that the long-run average of $g(y_t')$ is $\bar g(R)/Q$; Proposition 5.1 in the same ergodic form for the $(R,Q)$ policy; and the two halves of the goal as separate statements.

Significance

The result itself. Proposition 6.1 is what licenses the two-parameter policies on which the rest of the book's single-echelon theory is built, and it does so for the practically important case of batch ordering (pallets, containers, production lots). Its proof also explains why the policy works: the only quantity a policy controls is the residue class of the inventory position modulo $Q$, which no policy can influence, and the position within that class, which the $(R,Q)$ policy always sets to the cheapest possible value. The book extends the same reasoning to other cost structures and to periodic review.

Formalizing it. The proposition is a theorem about the class of all policies, and the book's proof is pathwise: Lemma 6.1 compares any policy with the reduced process instant by instant, and an ergodic statement about the reduced process does the rest. Formalizing it therefore forces the policy class, the demand process and the long-run average to be written down exactly, which the book never does. Nothing here is open; no statement has a machine-checked proof yet.

Difficulty

The pointwise comparison is elementary once Lemma 6.1 is available, and Lemma 6.1 is discrete convexity. The difficulty is entirely in the ergodic statement: that the reduced position $y_t' =$ (the band representative of $y_0 - S_{N(t)}$) spends a fraction $1/Q$ of the time at each point of the band, almost surely. In discrete time this is the convergence of occupation frequencies for an irreducible random walk on $\mathbb{Z}/Q\mathbb{Z}$ with step law $f$ modulo $Q$, where irreducibility is exactly the aperiodicity assumption on $f$, and the book's double-stochasticity argument (Eq. 5.33-5.34) identifies the uniform law as stationary. Passing to continuous time adds the exponential holding times: the time average is the arrival average weighted by i.i.d. holding times independent of the walk, which a strong law of large numbers turns back into the discrete statement. Mathlib has the strong law and the exponential law but no ergodic theorem for finite Markov chains, so that is the groundwork a solver must build. The naive route through the stationary distribution of the embedded chain at demand epochs is not enough on its own: for pure Poisson demand that chain is periodic, and the book itself notes it.

Formalization scope

A CompoundPoissonDemand on a probability space packages the rate, the size law with $f_0 = 0$ and the aperiodicity condition, and two sequences of random variables, the gaps and the sizes, with their laws (expMeasure lam, the given pmf), independence within each sequence, and independence between the sequences. Arrival times are partial sums of the gaps, count t is the supremum of $\{n : T_n \le t\}$, and cumDemand n is the partial sum of the sizes. A policy is a function m : ℕ → Ω → ℕ with no measurability requirement; ipPath and ipAt are the position after the $n$-th demand and at time $t$; rqIP and rqOrders are the $(R,Q)$ policy, with a theorem identifying rqOrders as a policy in the general sense. avgCost is $\frac{1}{T}\int_0^T g(y_{t-L})\,\mathrm{d}t$ with $y_s = y_0$ for $s < 0$. The cost function $g$ is sPolicyCost from the previous mission, applied to a DiscreteDemand that the hypotheses tie to the process as the law of the demand in $(0, L]$.

Conventions: $Q \ge 1$, $L \ge 0$, $h, b_1 > 0$; $R$ is any minimizer of $\bar g$ (it exists by the divergence of $g$, proved in the previous mission); $y_0$ is arbitrary. count and the interval integral take junk values on the null set where arrivals do not tend to infinity, which the almost-sure conclusions absorb. "$\liminf \ge c$" is stated as "for every $\varepsilon > 0$, eventually $\ge c - \varepsilon$", avoiding a liminf on $\mathbb{R}$ that could be junk.

Two readings that would trivialize the goal are excluded: the lower bound is over every rule, not over stationary or measurable ones, and the achievability half is a genuine limit, not a bound. The demand model and the occupation-frequency theorems are reusable for Proposition 10.1 and the batch-ordering models of Sect. 10.5; contributions establishing the ergodic theorem for irreducible chains on a finite cyclic group are welcome and would close most of this mission.

Selected references

• Sven Axsäter, Inventory Control, 3rd edition, International Series in Operations Research & Management Science 225, Springer, 2015, Sects. 5.3.1 and 6.2.1. DOI 10.1007/978-3-319-15729-0
• Fangruo Chen, Optimal Policies for Multi-Echelon Inventory Problems with Batch Ordering, Operations Research 48(3), 2000, pp. 376-389. DOI 10.1287/opre.48.3.376.12427
• Awi Federgruen and Yu-Sheng Zheng, An Efficient Algorithm for Computing an Optimal $(r,Q)$ Policy in Continuous Review Stochastic Inventory Systems, Operations Research 40(4), 1992, pp. 808-813. DOI 10.1287/opre.40.4.808
• Evan L. Porteus, Foundations of Stochastic Inventory Theory, Stanford University Press, 2002.

Two decisions that are usually taken separately

An $(R,Q)$ policy has two parameters. Chapter 4 of Axsäter's Inventory Control chooses the batch quantity $Q$ from a deterministic model, and Chapter 5 chooses the reorder point $R$ from a stochastic one with $Q$ held fixed; the book presents this two-step practice as an adequate approximation. Section 6.1 asks what is lost by it and shows how to optimize both parameters jointly in one stochastic model. For discrete demand the answer, due to Federgruen and Zheng (1992), is an algorithm of remarkable simplicity: increase $Q$ one unit at a time, keep the reorder point optimal along the way by a one-line rule, and stop at the first $Q$ for which the cost goes up. The claim that this stopping rule finds the global optimum over all pairs $(R, Q)$ is the capstone of Sect. 6.1.1.1 and the goal of this mission. The same idea is reused in the book for $(s,S)$ policies (Sect. 6.1.1.2) and, in continuous form, for normally distributed demand (Sect. 6.1.2).

Setting

An item is controlled by a continuous review $(R,Q)$ policy with integral reorder point $R$ and batch quantity $Q \ge 1$. Demand is discrete and stationary; the lead-time demand $D(L)$ takes values in the nonnegative integers with probabilities $p_j = \Pr[D(L) = j]$ and has a finite mean $\mu'$. The average demand per unit of time is $\mu$. Costs are a holding cost $h$ and a shortage cost $b_1$, both per unit and time unit, and an ordering cost $A$ per batch.

The building block is the cost of an $(S-1,S)$ policy that keeps the inventory position at a fixed integer $k$. By the standard argument of Sect. 5.3.2 the inventory level a lead-time later is $k - D(L)$, and the average holding and shortage cost rate is (Eq. 6.3)

$$g(k) \;=\; -b_1\,(k - \mu') + (h + b_1)\sum_{j=1}^{k} j\,\Pr[D(L) = k - j].$$

Under the $(R,Q)$ policy the inventory position is uniformly distributed on $\{R+1, \dots, R+Q\}$ (Proposition 5.1), so the total average cost rate is (Eq. 6.4)

$$C(R, Q) \;=\; \frac{A\mu}{Q} + \frac{1}{Q}\sum_{k=R+1}^{R+Q} g(k),$$

and $C(Q) = \min_R C(R,Q)$ (Eq. 6.5), attained at an optimal reorder point $R^{*}(Q)$. The ready rate $S_3(R) = \Pr[IL > 0] = \frac{1}{Q}\sum_{k=R+1}^{R+Q}\Pr[D(L) \le k-1]$ links the cost to service: raising the reorder point by one unit changes the cost by $-b_1 + (h + b_1)S_3(R+1)$ (Eq. 5.60).

Formalization targets

Goal — the Federgruen-Zheng stopping rule is optimal

Let $Q^{*} \ge 1$ be the smallest batch quantity with $C(Q^{*}+1) \ge C(Q^{*})$ and let $R^{*}$ be an optimal reorder point for $Q^{*}$. Then

$$C(R^{*}, Q^{*}) \;\le\; C(R, Q) \qquad\text{for all } R \in \mathbb{Z},\ Q \ge 1.$$

Supporting targets

The increment identity $g(k+1) - g(k) = -b_1 + (h+b_1)\Pr[D(L) \le k]$; convexity of $g$ on $\mathbb{Z}$ together with $g(k) \to \infty$ as $|k| \to \infty$; Eq. (5.60) and the convexity of $C(\cdot, Q)$ in $R$; Eq. (5.61), that the largest $R$ with $S_3(R) \le b_1/(h+b_1)$ is optimal for its $Q$; existence of an optimal $R$ for every $Q$; the recursion (6.6)-(6.7), $R^{*}(Q+1) \in \{R^{*}(Q) - 1, R^{*}(Q)\}$ chosen by comparing $g(R^{*}(Q))$ with $g(R^{*}(Q)+Q+1)$, and $C(Q+1) = C(Q)\frac{Q}{Q+1} + \min\{g(R^{*}(Q)), g(R^{*}(Q)+Q+1)\}\frac{1}{Q+1}$; the equivalence $C(Q+1) \ge C(Q) \iff \min\{\cdot\} \ge C(Q)$ and the monotonicity of that minimum in $Q$; and the existence of some $Q$ at which the costs stop decreasing.

Significance

The result itself. Joint optimization typically enlarges the batch and lowers the reorder point relative to the two-step procedure, and the book's Example 6.1 puts the resulting cost saving at a few percent. The Federgruen-Zheng procedure makes the exact joint optimum for discrete demand as cheap to compute as the two-step approximation, because each step of the recursion evaluates $g$ at two points. It is the exact benchmark against which the book's approximate techniques for normal demand (Sects. 6.1.2 and 6.1.3) are judged, and its structural core, that the optimal window of $Q$ consecutive inventory positions grows one neighbour at a time, is the discrete-convexity fact behind the whole of Sect. 6.1.

Formalizing it. The mathematics is settled. What the mission produces is a Lean development in which the steps the book marks "evident" and "obvious" are separate statements: that the recursion preserves optimality, that the marginal cost of enlarging the batch is monotone, and that a minimum over $R$ exists at all. None of the statements has a machine-checked proof yet.

Difficulty

The obvious first idea, to argue that $C(Q)$ is convex in $Q$ and stop at its first increase, does not work as stated: $C(Q)$ is a minimum over $R$ of a ratio and is not convex in general. What is true, and what the proof uses, is that the marginal cost $(Q+1)C(Q+1) - QC(Q)$ is nondecreasing, because it equals the smaller of the two $g$-values adjacent to the optimal window. Establishing the recursion (6.6) is where discrete convexity is needed: one must show that the best window of $Q+1$ consecutive positions is obtained from the best window of $Q$ by adding a neighbour, which fails for non-convex $g$. The window sums $R \mapsto \sum_{k=R+1}^{R+Q} g(k)$ are themselves convex in $R$ with increments $g(R+Q+1) - g(R+1)$, and the argument compares a competing window with the optimal one through the end terms. The remaining steps are finite algebra and an induction on $Q$ from $Q^{*}$.

Formalization scope

A DiscreteDemand is a function $p : \mathbb{N} \to \mathbb{R}$ with $p \ge 0$, $\sum p = 1$ and a summable first moment; $\Pr[D(L) \le k]$ is a finite sum over $0 \le j \le k$, empty for $k < 0$. The reorder point ranges over $\mathbb{Z}$ and the batch quantity over $\mathbb{N}$, with $Q \ge 1$ assumed in every statement because Lean's division by $0$ is $0$. Convexity of a function on $\mathbb{Z}$ is stated as nondecreasing increments, and divergence as Tendsto g (cocompact ℤ) atTop.

$C(Q)$ enters the goal as a function CQ together with the hypothesis that CQ Q is the least value of $R \mapsto C(R, Q)$; the stopping index $Q^{*}$ is characterized by the two conditions that define "the smallest $Q$ with $C(Q+1) \ge C(Q)$", and $R^{*}$ by optimality at $Q^{*}$. That these objects exist is the content of two separate items, so the goal is not vacuous: a minimum over $R$ exists for every $Q$ because $g \to \infty$, and the costs cannot decrease forever because the average of the $Q$ smallest values of $g$ tends to infinity. The positivity of $A$ and $\mu$ is the book's setting and is assumed where it appears.

The uniform inventory position of Proposition 5.1, which needs the book's assumption that not all demands are multiples of an integer larger than one, is taken as given in the cost formula (6.4), as the book does; the proposition itself is the subject of the next mission of this series. The definitions are reusable for the $(s,S)$ optimization of Sect. 6.1.1.2 and for the multi-echelon batch-ordering results of Sect. 10.5; contributions formalizing the Zheng-Federgruen $(s,S)$ algorithm on top of them are welcome.

Selected references

• Sven Axsäter, Inventory Control, 3rd edition, International Series in Operations Research & Management Science 225, Springer, 2015, Sects. 5.9.1 and 6.1.1. DOI 10.1007/978-3-319-15729-0
• Awi Federgruen and Yu-Sheng Zheng, An Efficient Algorithm for Computing an Optimal $(r,Q)$ Policy in Continuous Review Stochastic Inventory Systems, Operations Research 40(4), 1992, pp. 808-813. DOI 10.1287/opre.40.4.808
• Yu-Sheng Zheng and Awi Federgruen, Finding Optimal $(s,S)$ Policies Is About as Simple as Evaluating a Single Policy, Operations Research 39(4), 1991, pp. 654-665. DOI 10.1287/opre.39.4.654
• Paul Zipkin, Foundations of Inventory Management, McGraw-Hill, 2000.

Where the reorder point comes from

Chapter 4 of Axsäter's Inventory Control fixes the batch quantity $Q$ from a deterministic model, and Chapter 5 asks the question that deterministic models cannot answer: with demand random and a replenishment lead-time $L$, when should the next batch be ordered? Under a continuous review $(R,Q)$ policy the answer is a single number, the reorder point $R$, and Sections 5.3 through 5.9 are one sustained computation of what a given $R$ buys. The chapter's own capstone is Eq. (5.67): if backorders are charged at $b_1$ per unit and time unit and stock at $h$, the cost-minimizing reorder point is exactly the one whose fill rate is $b_1/(h+b_1)$. The book calls the relationship "even more striking" than its discrete counterpart, and it is used in practice in both directions: a backorder cost prescribes a service level, and a chosen service level reveals the backorder cost a planner is implicitly assuming (Eq. 5.68).

Setting

An order for a fixed batch quantity $Q > 0$ is triggered whenever the inventory position (stock on hand plus outstanding orders minus backorders) falls to the reorder point $R$, and it arrives $L$ time units later. Demand is continuous and normally distributed; the demand over a lead-time has mean $\mu'$ and standard deviation $\sigma' > 0$. Two modelling facts from the book are taken as the definition of the steady state. First (Sect. 5.3.1), the inventory position $IP$ is uniformly distributed on $[R, R+Q]$; the book proves this for compound Poisson demand (Proposition 5.1) and adopts it as an accurate approximation for continuous demand. Second (Sect. 5.3.2, Eq. 5.35), the inventory level a lead-time later is the inventory position now minus the demand in between,

$$IL(t+L) \;=\; IP(t) - D(t, t+L),$$

with the two terms independent. The law of $IL$ is therefore the image of the product of a uniform and a normal law under subtraction, and everything in the chapter is a functional of it:

• the distribution function $F(x) = \Pr[IL \le x]$ and its density $f$;
• the ready rate $S_3 = \Pr[IL > 0]$, which for continuous demand equals the fill rate $S_2$, the fraction of demand met from stock on hand;
• the expected cost rate $C(R) = \mathbb{E}\big[h\,(IL)^{+} + b_1\,(IL)^{-}\big]$, holding cost on positive stock and backorder cost on negative stock, Eq. (5.56).

The closed forms run through the standard normal loss function $G(x) = \int_x^\infty (v-x)\varphi(v)\,\mathrm{d}v$ of Eq. (5.40), published with the newsboy mission and reused here, and through its integral, the second loss function $H(x) = \int_x^\infty G(v)\,\mathrm{d}v$ of Eq. (5.64). Both are tabulated in the book's Appendix 2, and both recur in Chapters 6, 9 and 10.

Formalization targets

Goal — Eq. (5.67)

For $h, b_1, Q, \sigma' > 0$ and any $\mu'$, a reorder point $R$ minimizes $C$ over $\mathbb{R}$ if and only if

$$S_2(R) \;=\; S_3(R) \;=\; \frac{b_1}{h + b_1}.$$

The biconditional carries both halves of the book's sentence: the stationary point is the optimum ("the optimal $R$ is obtained for $\mathrm{d}C/\mathrm{d}R = 0$") and the optimum is stationary ("in the optimal solution we have $S_2 = S_3 = b_1/(h+b_1)$").

Supporting targets

In the order the chapter builds them: Eq. (5.41), $G' = \Phi - 1$, with $G$ decreasing and convex; Eq. (5.39), the distribution function by conditioning on the inventory position; Eq. (5.42), its closed form $F(x) = \frac{\sigma'}{Q}[G(\frac{R-x-\mu'}{\sigma'}) - G(\frac{R+Q-x-\mu'}{\sigma'})]$; Eq. (5.43), the density; Eq. (5.52), the fill rate $1 - \frac{\sigma'}{Q}[G(\frac{R-\mu'}{\sigma'}) - G(\frac{R+Q-\mu'}{\sigma'})]$; Eq. (5.55), the expected backorders $\mathbb{E}(B)$ covered by one batch, and Eq. (5.54), that $1 - \mathbb{E}(B)/Q$ is the same fill rate; integrability of the cost rate and the mean $\mathbb{E}(IL) = R + Q/2 - \mu'$; Eq. (5.63), $\mathbb{E}(IL)^{-} = \int_{-\infty}^0 F$; Eq. (5.64), the closed form of $H$ and $H' = -G$; Eq. (5.65), the cost $C = h(R + Q/2 - \mu') + (h+b_1)\frac{\sigma'^2}{Q}[H(\frac{R-\mu'}{\sigma'}) - H(\frac{R+Q-\mu'}{\sigma'})]$; Eq. (5.66), $\mathrm{d}C/\mathrm{d}R = -b_1 + (h+b_1)S_2$; and the convexity of $C$ in $R$.

Significance

The result itself. The reorder point is the one parameter of an $(R,Q)$ policy that stochastic demand actually decides, and Eq. (5.67) says that deciding it by cost and deciding it by service level are the same decision, with an explicit dictionary between the two. That is why the book can present service-level constraints (Sect. 5.7) and shortage costs (Sect. 5.9) as interchangeable ways of specifying the same thing, and why it warns, immediately after Eq. (5.67), that the equivalence is only valid when $Q$ is given: with an ordering cost and a joint optimization of $R$ and $Q$ it fails, which is Chapter 6's problem.

The intermediate formulas have independent standing. Eq. (5.42) is the single expression from which every service measure of the chapter is computed, and Eq. (5.65) is the cost function that Chapter 6 extends by an ordering cost, Eq. (6.10), and optimizes iteratively. The second loss function $H$ returns in the periodic-review fill rate of Eq. (5.86) and in the two-echelon batch-ordering model of Sect. 10.5.

Formalizing it. Nothing here is open; the value is that the steady-state model becomes an explicit measure, so that formulas the book obtains by manipulating integrals whose existence it never questions become theorems about that measure. Integrability of the cost rate is a target of its own for exactly that reason. None of the statements has a machine-checked proof yet.

Difficulty

The obvious route is the book's, and it is not the hard part: once $F$ is known in closed form, every later identity is calculus on $G$ and $H$. The work is upstream of that. The distribution function (5.39) is a conditioning argument over the product measure, a Fubini step in which the inner probability is a Gaussian tail; the density (5.43) is a derivative of a parameter-dependent integral; and Eq. (5.63) exchanges the order of two integrals over an unbounded region, which needs integrability of $IL$ itself. The derivative (5.66) is then obtained from the closed form (5.65), not by differentiating under an expectation, which is what makes the goal reachable: $C$ is a smooth function of $R$ with an explicitly increasing derivative, and Eq. (5.67) follows from strict convexity together with the fact that the fill rate is a continuous, strictly increasing function of $R$ ranging over $(0,1)$. A solver who starts from the expectation and tries to differentiate it directly will meet the kink of $x^{+}$ at $0$ and a dominated-convergence argument; the integrated route avoids both.

Formalization scope

The inventory position is rqPosition R Q, Lebesgue measure conditioned on $[R, R+Q]$; the lead-time demand is newsboyDemand m s, Mathlib's gaussianReal m (s^2).toNNReal from the newsboy mission, with $m = \mu'$ and $s = \sigma'$; and rqLevel R Q m s is the pushforward of their product under $(u, d) \mapsto u - d$. Two lemmas in the definition file record that both are probability measures when $Q > 0$. The distribution function, ready rate and cost are the measure of $(-\infty, x]$, the measure of $(0, \infty)$, and a Bochner integral against this law.

Every statement assumes $Q > 0$ and $\sigma' > 0$. At $Q = 0$ the conditioned measure is the zero measure and every integral is $0$, so a statement without the hypothesis would be true and empty; at $\sigma' = 0$ the demand is a point mass and $F$ has jumps. The mean $\mu'$ is unrestricted, as none of the formulas depends on its sign, and reorder points may be negative, which the book explicitly allows in Sect. 5.8. Costs $h$ and $b_1$ are positive in every statement that involves them, and $\mathbb{E}(B)$ is stated for $Q \ge 0$ because its closed form holds there.

Two trivializing readings are ruled out. The cost is not defined as a formula in $H$ but as an expectation, so the closed form (5.65) has content; and because Lean's Bochner integral of a non-integrable function is $0$, integrability of the cost rate is stated as a theorem rather than assumed, otherwise a zero cost would make every reorder point optimal. The goal quantifies optimality over all real competing reorder points, not a neighbourhood.

A complete development needs Gaussian tail integrals, differentiation of parameter-dependent integrals, Fubini on a product of a bounded interval with the line, and the strict monotonicity of the Gaussian distribution function. The loss functions $G$ and $H$ and the inventory-level law are reusable across the rest of the series; contributions that establish the same identities for an arbitrary continuous lead-time demand with a finite mean, where Eqs. (5.39), (5.63) and (5.66) hold verbatim, are welcome.

Selected references

• Sven Axsäter, Inventory Control, 3rd edition, International Series in Operations Research & Management Science 225, Springer, 2015, Sects. 5.3, 5.7, 5.8 and 5.9. DOI 10.1007/978-3-319-15729-0
• George Hadley and Thomson M. Whitin, Analysis of Inventory Systems, Prentice-Hall, 1963.
• Paul Zipkin, Foundations of Inventory Management, McGraw-Hill, 2000.
• Yu-Sheng Zheng, On Properties of Stochastic Inventory Systems, Management Science 38(1), 1992, pp. 87-103. DOI 10.1287/mnsc.38.1.87
• Kaj Rosling, Inventory Cost Rate Functions with Nonlinear Shortage Costs, Operations Research 50(6), 2002, pp. 1007-1017. DOI 10.1287/opre.50.6.1007.346