Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

General FIFO guarantee: C(πFIFO)≤γ OPTC(\pi_{\rm FIFO})\le\gamma\,\mathrm{OPT}C(πFIFO​)≤γOPT (Theorem 1)

Proved
OWMR.general_fifo_guarantee

by Ming Hu · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsinventoryinventory-theoryoperations-researchstochastic-control

Let m≥1m\ge1m≥1, define γm:=9/4+1/(4m)\gamma_m:=9/4+1/(4m)γm​:=9/4+1/(4m), and let γ≥γm\gamma\ge\gamma_mγ≥γm​. Consider an OWMR network with n≥1n\ge1n≥1 retailers that satisfies the standing assumptions: demand vectors i.i.d. over periods with nonnegative components and 0<EDi,t<∞0<\mathbb E D_{i,t}<\infty0<EDi,t​<∞, setup costs K0,Ki≥0K_0,K_i\ge0K0​,Ki​≥0, and h,Hi,p>0h,H_i,p>0h,Hi​,p>0. Suppose

  1. Hi≥mhH_i\ge mhHi​≥mh for every retailer iii,
  2. p≥hp\ge hp≥h, and
  3. Kmax⁡≤(γ−1)K0K_{\max}\le(\gamma-1)K_0Kmax​≤(γ−1)K0​, where Kmax⁡=max⁡iKiK_{\max}=\max_iK_iKmax​=maxi​Ki​.

Then, from every valid initial state and at all finite supplier and retailer lead times, the deterministic FIFO policy πFIFO\pi_{\rm FIFO}πFIFO​ of Definition 1 satisfies

C(πFIFO)≤γ OPT.C(\pi_{\rm FIFO})\le\gamma\,\mathrm{OPT}.C(πFIFO​)≤γOPT.

Taking m=1m=1m=1 and γ=γ1=5/2\gamma=\gamma_1=5/2γ=γ1​=5/2 gives C(πFIFO)≤52 OPTC(\pi_{\rm FIFO})\le\frac52\,\mathrm{OPT}C(πFIFO​)≤25​OPT when Hi≥hH_i\ge hHi​≥h, p≥hp\ge hp≥h, and Ki≤3K0/2K_i\le3K_0/2Ki​≤3K0​/2 for every iii. This is the main result of the source: a constant factor for an echelon stock (s,S)(s,S)(s,S) policy relative to all nonanticipative policies, independent of the lead times and the number of retailers.

Formalization Note The conclusion holds for every admissible choice in Definition 1 (IsFIFOChoice N c). C(πFIFO)C(\pi_{\rm FIFO})C(πFIFO​) and OPT\mathrm{OPT}OPT take values in [0,∞][0,\infty][0,∞], and γ>0\gamma>0γ>0 enters through ENNReal.ofReal.

Preamble
import Definitions.Def_owmr_fifo_policy

open scoped ENNReal
Formal statement
namespace OWMR
theorem general_fifo_guarantee {n : ℕ} (hn : 0 < n) (N : Network n) (hN : N.Standing)
    (m γ : ℝ) (hm : 1 ≤ m) (hγ : 9 / 4 + 1 / (4 * m) ≤ γ)
    (hH : ∀ i, m * N.h ≤ N.H i) (hp : N.h ≤ N.p) (hK : N.Kmax ≤ (γ - 1) * N.K0)
    (x : InitState n) (hx : x.Valid) (c : FIFOChoice n) (hc : IsFIFOChoice N c) :
    (fifoPolicy N x c).avgCost N x ≤ ENNReal.ofReal γ * OPT N x := by sorry
end OWMR
Source
M. Hu, "A 5/2 Guarantee for Echelon Stock (s,S) Policies in One-Warehouse Multi-Retailer Systems", working paper (manuscript of November 2026), Section 3, Theorem 1 (General FIFO Guarantee), p. 9.
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Bottom line. For every n≥1n\ge 1n≥1, every network NNN with nnn retailers that satisfies the standing assumptions, all reals m,γm,\gammam,γ with m≥1m\ge 1m≥1 and γ≥94+14m\gamma\ge \tfrac{9}{4}+\tfrac{1}{4m}γ≥49​+4m1​ such that Hi≥m hH_i\ge m\,hHi​≥mh for all iii, h≤ph\le ph≤p and Kmax⁡≤(γ−1)K0K_{\max}\le(\gamma-1)K_0Kmax​≤(γ−1)K0​, every valid initial state xxx, and every parameter vector ccc that satisfies the FIFO-choice predicate for NNN, the statement asserts

CN,x(πN,x,cFIFO) ≤ γ⋅OPT(N,x),\mathcal{C}_{N,x}\big(\pi^{\mathrm{FIFO}}_{N,x,c}\big)\ \le\ \gamma\cdot \mathrm{OPT}(N,x),CN,x​(πN,x,cFIFO​) ≤ γ⋅OPT(N,x),

as an inequality in [0,∞][0,\infty][0,∞]. The left side is the upper-limit long-run average expected cost of one specific deterministic policy built from (N,x,c)(N,x,c)(N,x,c). The right side is γ\gammaγ times the infimum of the same cost functional over all randomized, nonanticipative, measurable, feasible policies started from the same xxx. The constant enters as ofReal(γ)=max⁡(γ,0)\mathrm{ofReal}(\gamma)=\max(\gamma,0)ofReal(γ)=max(γ,0), which equals γ\gammaγ because γ>94\gamma>\tfrac{9}{4}γ>49​. Words such as warehouse, retailer, order, dispatch and request are labels taken from identifier names. Every object is defined by the formulas below.

Binders and hypotheses (all universally quantified, and there are no others).

  • n∈Nn\in\mathbb{N}n∈N with 0<n0<n0<n. Retailers are written i=1,…,ni=1,\dots,ni=1,…,n here. The code indexes them 0,…,n−10,\dots,n-10,…,n−1, and their order matters only for tie-breaking in the FIFO queue.
  • A network N=(L0,(Li),μ,K0,(Ki),h,(Hi),p)N=(L_0,(L_i),\mu,K_0,(K_i),h,(H_i),p)N=(L0​,(Li​),μ,K0​,(Ki​),h,(Hi​),p), and the hypothesis that NNN satisfies the standing assumptions.
  • m,γ∈Rm,\gamma\in\mathbb{R}m,γ∈R with 1≤m1\le m1≤m and 94+14m≤γ\tfrac{9}{4}+\tfrac{1}{4m}\le\gamma49​+4m1​≤γ.
  • m h≤Him\,h\le H_imh≤Hi​ for every iii; h≤ph\le ph≤p; Kmax⁡≤(γ−1) K0K_{\max}\le(\gamma-1)\,K_0Kmax​≤(γ−1)K0​.
  • An initial state xxx, and the hypothesis that xxx is valid.
  • A parameter vector ccc, and the hypothesis that ccc satisfies the FIFO-choice predicate for NNN.

Network, standing assumptions, Kmax⁡K_{\max}Kmax​. L0,Li∈NL_0,L_i\in\mathbb{N}L0​,Li​∈N, with zero allowed and no other constraint. μ\muμ is a probability measure on [0,∞)n[0,\infty)^n[0,∞)n: the law of one period's demand vector ξ=(ξ1,…,ξn)\xi=(\xi_1,\dots,\xi_n)ξ=(ξ1​,…,ξn​), with any dependence across retailers. K0,Ki,h,Hi,pK_0,K_i,h,H_i,pK0​,Ki​,h,Hi​,p are reals. Demands in different periods are i.i.d. with law μ\muμ, because every cost functional below uses product measures. The standing assumptions are exactly:

  • 0<Eμ[ξi]<∞0<\mathbb{E}_\mu[\xi_i]<\infty0<Eμ​[ξi​]<∞ for every iii, computed as a [0,∞][0,\infty][0,∞]-valued integral;
  • K0≥0K_0\ge0K0​≥0 and Ki≥0K_i\ge0Ki​≥0;
  • h>0h>0h>0, Hi>0H_i>0Hi​>0 and p>0p>0p>0.

Kmax⁡K_{\max}Kmax​ is the real supremum of the family (Ki)i(K_i)_i(Ki​)i​. Since n≥1n\ge1n≥1 it equals max⁡iKi\max_i K_imaxi​Ki​. For an empty family, the real supremum would be the conventional value 000.

Initial state and validity. x=(W,I,α,β)x=(W,I,\alpha,\beta)x=(W,I,α,β) with W∈RW\in\mathbb{R}W∈R, I=(Ii)∈RnI=(I_i)\in\mathbb{R}^nI=(Ii​)∈Rn, α:N→R\alpha:\mathbb{N}\to\mathbb{R}α:N→R and βi:N→R\beta_i:\mathbb{N}\to\mathbb{R}βi​:N→R. Only αt\alpha_tαt​ for t<L0t<L_0t<L0​ and βi,t\beta_{i,t}βi,t​ for t<Lit<L_it<Li​ are ever used, as exogenous arrivals in period ttt. Valid means W≥0W\ge0W≥0, αt≥0\alpha_t\ge0αt​≥0 for all t∈Nt\in\mathbb{N}t∈N, and βi,t≥0\beta_{i,t}\ge0βi,t​≥0 for all i,ti,ti,t, unused entries included. There is no condition on III, so negative IiI_iIi​ are allowed.

Cost functional (used on both sides). A policy on a measurable space UUU is any pair of real-valued maps ordt(u,d)\mathrm{ord}_t(u,d)ordt​(u,d) and dispt,i(u,d)\mathrm{disp}_{t,i}(u,d)dispt,i​(u,d), t∈Nt\in\mathbb{N}t∈N. Here d=(d0,d1,… )d=(d_0,d_1,\dots)d=(d0​,d1​,…) is a demand path with dt=(dt,1,…,dt,n)∈[0,∞)nd_t=(d_{t,1},\dots,d_{t,n})\in[0,\infty)^ndt​=(dt,1​,…,dt,n​)∈[0,∞)n. Given xxx, the arrivals are:

  • at the warehouse, At0=αtA^0_t=\alpha_tAt0​=αt​ for t<L0t<L_0t<L0​ and At0=ordt−L0A^0_t=\mathrm{ord}_{t-L_0}At0​=ordt−L0​​ for t≥L0t\ge L_0t≥L0​;
  • at retailer iii, Ati=βi,tA^i_t=\beta_{i,t}Ati​=βi,t​ for t<Lit<L_it<Li​ and Ati=dispt−Li,iA^i_t=\mathrm{disp}_{t-L_i,i}Ati​=dispt−Li​,i​ for t≥Lit\ge L_it≥Li​.

From these,

Wt=W+∑r=0t(Ar0−∑idispr,i),Wtav=W+∑r=0t−1(Ar0−∑idispr,i)+At0,Ii,t=Ii+∑r=0t(Ari−dr,i),W_t=W+\sum_{r=0}^{t}\Big(A^0_r-\sum_{i}\mathrm{disp}_{r,i}\Big),\qquad W^{\mathrm{av}}_t=W+\sum_{r=0}^{t-1}\Big(A^0_r-\sum_{i}\mathrm{disp}_{r,i}\Big)+A^0_t,\qquad I_{i,t}=I_i+\sum_{r=0}^{t}\big(A^i_r-d_{r,i}\big),Wt​=W+r=0∑t​(Ar0​−i∑​dispr,i​),Wtav​=W+r=0∑t−1​(Ar0​−i∑​dispr,i​)+At0​,Ii,t​=Ii​+r=0∑t​(Ari​−dr,i​), ct=K0 1[ordt>0]+∑iKi 1[dispt,i>0]+h Wt+∑i(Hi Ii,t++p Ii,t−),c_t=K_0\,\mathbf{1}[\mathrm{ord}_t>0]+\sum_i K_i\,\mathbf{1}[\mathrm{disp}_{t,i}>0]+h\,W_t+\sum_i\big(H_i\,I_{i,t}^{+}+p\,I_{i,t}^{-}\big),ct​=K0​1[ordt​>0]+i∑​Ki​1[dispt,i​>0]+hWt​+i∑​(Hi​Ii,t+​+pIi,t−​),

with y+=max⁡(y,0)y^+=\max(y,0)y+=max(y,0) and y−=max⁡(−y,0)y^-=\max(-y,0)y−=max(−y,0). The warehouse term is h Wth\,W_thWt​, not h Wt+h\,W_t^+hWt+​. For a probability measure ν\nuν on UUU,

CN,x(π,ν)=lim sup⁡T→∞ 1T∫∑t=0T−1max⁡(ct(u,zˉ),0) (ν⊗μ⊗T)(du,dz) ∈[0,∞],\mathcal{C}_{N,x}(\pi,\nu)=\limsup_{T\to\infty}\ \frac{1}{T}\int\sum_{t=0}^{T-1}\max\big(c_t(u,\bar z),0\big)\,(\nu\otimes\mu^{\otimes T})(du,dz)\ \in[0,\infty],CN,x​(π,ν)=T→∞limsup​ T1​∫t=0∑T−1​max(ct​(u,zˉ),0)(ν⊗μ⊗T)(du,dz) ∈[0,∞],

where z=(z0,…,zT−1)z=(z_0,\dots,z_{T-1})z=(z0​,…,zT−1​) and zˉ\bar zzˉ is the path z0,…,zT−1,0,0,…z_0,\dots,z_{T-1},0,0,\dotsz0​,…,zT−1​,0,0,…. This means:

  • uuu is drawn once from ν\nuν, independently of the demands;
  • each period cost is truncated below at 000 before summing;
  • the integral of the [0,∞][0,\infty][0,∞]-valued integrand is taken in the lower-integral sense (the supremum of integrals of measurable simple functions below it). This is the usual integral when the integrand is measurable, and it is defined even when it is not.

For a deterministic policy, UUU is a one-point space with its Dirac measure. Then C\mathcal{C}C reduces to lim sup⁡T1T Ez∼μ⊗T∑t<Tmax⁡(ct(zˉ),0)\limsup_{T}\frac{1}{T}\,\mathbb{E}_{z\sim\mu^{\otimes T}}\sum_{t<T}\max(c_t(\bar z),0)limsupT​T1​Ez∼μ⊗T​∑t<T​max(ct​(zˉ),0). The left side of the theorem is this quantity for πN,x,cFIFO\pi^{\mathrm{FIFO}}_{N,x,c}πN,x,cFIFO​.

The optimum OPT(N,x)\mathrm{OPT}(N,x)OPT(N,x). It is the infimum in [0,∞][0,\infty][0,∞] of CN,x(π,ν)\mathcal{C}_{N,x}(\pi,\nu)CN,x​(π,ν) over every measurable space UUU, every probability measure ν\nuν on UUU, and every policy π\piπ on UUU that is:

  • nonanticipative: ordt(u,d)\mathrm{ord}_t(u,d)ordt​(u,d) and dispt,i(u,d)\mathrm{disp}_{t,i}(u,d)dispt,i​(u,d) depend on ddd only through d0,…,dt−1d_0,\dots,d_{t-1}d0​,…,dt−1​;
  • measurable: for each ttt and iii, the maps (u,d)↦ordt(u,d)(u,d)\mapsto\mathrm{ord}_t(u,d)(u,d)↦ordt​(u,d) and (u,d)↦dispt,i(u,d)(u,d)\mapsto\mathrm{disp}_{t,i}(u,d)(u,d)↦dispt,i​(u,d) are measurable for the product σ\sigmaσ-algebra on U×([0,∞)n)NU\times([0,\infty)^n)^{\mathbb{N}}U×([0,∞)n)N;
  • feasible for xxx: for every uuu, every demand path ddd (not only almost every) and every ttt, ordt≥0\mathrm{ord}_t\ge0ordt​≥0, dispt,i≥0\mathrm{disp}_{t,i}\ge0dispt,i​≥0 for all iii, and ∑idispt,i≤Wtav\sum_i\mathrm{disp}_{t,i}\le W^{\mathrm{av}}_t∑i​dispt,i​≤Wtav​.

For valid xxx this class is nonempty, since the policy that never orders or dispatches belongs to it. Feasibility gives Wt=Wtav−∑idispt,i≥0W_t=W^{\mathrm{av}}_t-\sum_i\mathrm{disp}_{t,i}\ge0Wt​=Wtav​−∑i​dispt,i​≥0. So under the standing sign conditions every ct≥0c_t\ge0ct​≥0 for these policies, and the truncation has no effect on the right side.

Single-location ingredients of the choice predicate. Let ρi\rho_iρi​ be the law of ξi\xi_iξi​ and ρΣ\rho_\SigmaρΣ​ the law of ξ1+⋯+ξn\xi_1+\dots+\xi_nξ1​+⋯+ξn​, both under μ\muμ. Define

Fi(y)=E[Hi (y−Zi)++p (Zi−y)+],Zi=sum of Li+1 i.i.d. draws from ρi,F_i(y)=\mathbb{E}\big[H_i\,(y-Z_i)^{+}+p\,(Z_i-y)^{+}\big],\qquad Z_i=\text{sum of }L_i+1\text{ i.i.d. draws from }\rho_i,Fi​(y)=E[Hi​(y−Zi​)++p(Zi​−y)+],Zi​=sum of Li​+1 i.i.d. draws from ρi​, f0(y)=E[h (y−Z0)++p (Z0−y)+],Z0=sum of L0 i.i.d. draws from ρΣ  (Z0=0 if L0=0).f_0(y)=\mathbb{E}\big[h\,(y-Z_0)^{+}+p\,(Z_0-y)^{+}\big],\qquad Z_0=\text{sum of }L_0\text{ i.i.d. draws from }\rho_\Sigma\ \ (Z_0=0\text{ if }L_0=0).f0​(y)=E[h(y−Z0​)++p(Z0​−y)+],Z0​=sum of L0​ i.i.d. draws from ρΣ​  (Z0​=0 if L0​=0).

These real-valued integrals would default to 000 for a non-integrable integrand, but the finite means make them genuine expectations.

Now take a probability law ρ\rhoρ on [0,∞)[0,\infty)[0,∞), a function f:R→Rf:\mathbb{R}\to\mathbb{R}f:R→R, reals K,s,SK,s,SK,s,S, and i.i.d. draws ζ0,ζ1,…\zeta_0,\zeta_1,\dotsζ0​,ζ1​,… from ρ\rhoρ. Run the (s,S)(s,S)(s,S) recursion: Y0=SY_0=SY0​=S; Y~t=S\tilde Y_t=SY~t​=S if Yt≤sY_t\le sYt​≤s, otherwise Y~t=Yt\tilde Y_t=Y_tY~t​=Yt​; Yt+1=Y~t−ζtY_{t+1}=\tilde Y_t-\zeta_tYt+1​=Y~t​−ζt​. Define

SSρ(f,K;s,S)=lim sup⁡T→∞1T E∑t=0T−1(K 1[Yt≤s and Yt<S]+f(Y~t))+,\mathrm{SS}_\rho(f,K;s,S)=\limsup_{T\to\infty}\frac{1}{T}\,\mathbb{E}\sum_{t=0}^{T-1}\Big(K\,\mathbf{1}[Y_t\le s\text{ and }Y_t<S]+f(\tilde Y_t)\Big)^{+},SSρ​(f,K;s,S)=T→∞limsup​T1​Et=0∑T−1​(K1[Yt​≤s and Yt​<S]+f(Y~t​))+, Vρ(f,K)=inf⁡ lim sup⁡T→∞1T E∑t=0T−1(K 1[qt>0]+f(yt))+,yt=∑r=0tqr−∑r=0t−1ζr.V_\rho(f,K)=\inf\ \limsup_{T\to\infty}\frac{1}{T}\,\mathbb{E}\sum_{t=0}^{T-1}\Big(K\,\mathbf{1}[q_t>0]+f(y_t)\Big)^{+},\qquad y_t=\sum_{r=0}^{t}q_r-\sum_{r=0}^{t-1}\zeta_r.Vρ​(f,K)=inf T→∞limsup​T1​Et=0∑T−1​(K1[qt​>0]+f(yt​))+,yt​=r=0∑t​qr​−r=0∑t−1​ζr​.

In VρV_\rhoVρ​ the infimum runs over every measurable space UUU, every probability ν\nuν on UUU (with u∼νu\sim\nuu∼ν independent of the ζ\zetaζ's), and every rule qt(u,ζ)∈Rq_t(u,\zeta)\in\mathbb{R}qt​(u,ζ)∈R that is nonanticipative (qtq_tqt​ depends only on ζ0,…,ζt−1\zeta_0,\dots,\zeta_{t-1}ζ0​,…,ζt−1​), jointly measurable, and ≥0\ge0≥0 for all t,u,ζt,u,\zetat,u,ζ. So this level starts at 000, while the (s,S)(s,S)(s,S) recursion starts at SSS. Further,

Mρ(h,p;s,S,a)=lim sup⁡T→∞1T E∑t=0T−1(h (a−Y~t)++p (Y~t−a)+)+,Mˉρ(h,p;s,S)=inf⁡a∈RMρ(h,p;s,S,a),\mathrm{M}_\rho(h,p;s,S,a)=\limsup_{T\to\infty}\frac{1}{T}\,\mathbb{E}\sum_{t=0}^{T-1}\Big(h\,(a-\tilde Y_t)^{+}+p\,(\tilde Y_t-a)^{+}\Big)^{+},\qquad \bar{\mathrm{M}}_\rho(h,p;s,S)=\inf_{a\in\mathbb{R}}\mathrm{M}_\rho(h,p;s,S,a),Mρ​(h,p;s,S,a)=T→∞limsup​T1​Et=0∑T−1​(h(a−Y~t​)++p(Y~t​−a)+)+,Mˉρ​(h,p;s,S)=a∈Rinf​Mρ​(h,p;s,S,a), Augi(s,S)=SSρi(Fi,Ki;s,S)+Mˉρi(h,p;s,S).\mathrm{Aug}_i(s,S)=\mathrm{SS}_{\rho_i}(F_i,K_i;s,S)+\bar{\mathrm{M}}_{\rho_i}(h,p;s,S).Augi​(s,S)=SSρi​​(Fi​,Ki​;s,S)+Mˉρi​​(h,p;s,S).

All of these lie in [0,∞][0,\infty][0,∞]. As on the network level, the horizon-TTT expectations are over TTT i.i.d. draws padded with zeros, and no term depends on the padding. In every instance used below, the per-period costs inside them are nonnegative under the standing assumptions, so the outer (⋅)+(\cdot)^+(⋅)+ has no effect.

A pair (sh,Sh)(s_h,S_h)(sh​,Sh​) is a canonical optimum for (ρ,f,K)(\rho,f,K)(ρ,f,K) if all of the following hold:

  • sh<Shs_h<S_hsh​<Sh​;
  • SSρ(f,K;sh,Sh)=Vρ(f,K)\mathrm{SS}_\rho(f,K;s_h,S_h)=V_\rho(f,K)SSρ​(f,K;sh​,Sh​)=Vρ​(f,K);
  • f(sh)+=Vρ(f,K)f(s_h)^+=V_\rho(f,K)f(sh​)+=Vρ​(f,K);
  • f(Sh)+≤Vρ(f,K)f(S_h)^+\le V_\rho(f,K)f(Sh​)+≤Vρ​(f,K);
  • f(y)+≤Vρ(f,K)f(y)^+\le V_\rho(f,K)f(y)+≤Vρ​(f,K) for all y∈[sh,Sh]y\in[s_h,S_h]y∈[sh​,Sh​].

The equality with the finite number f(sh)+f(s_h)^+f(sh​)+ forces Vρ(f,K)<∞V_\rho(f,K)<\inftyVρ​(f,K)<∞.

A pair (s′,S′)(s',S')(s′,S′) is a best half window of [sh,Sh][s_h,S_h][sh​,Sh​] for (ρ,f)(\rho,f)(ρ,f) if:

  • sh≤s′<S′≤Shs_h\le s'<S'\le S_hsh​≤s′<S′≤Sh​ and S′−s′=12(Sh−sh)S'-s'=\tfrac{1}{2}(S_h-s_h)S′−s′=21​(Sh​−sh​);
  • SSρ(f,0;s′,S′)≤SSρ(f,0;s′′,S′′)\mathrm{SS}_\rho(f,0;s',S')\le\mathrm{SS}_\rho(f,0;s'',S'')SSρ​(f,0;s′,S′)≤SSρ​(f,0;s′′,S′′) for every pair (s′′,S′′)(s'',S'')(s′′,S′′) with sh≤s′′<S′′≤Shs_h\le s''<S''\le S_hsh​≤s′′<S′′≤Sh​ and S′′−s′′=12(Sh−sh)S''-s''=\tfrac{1}{2}(S_h-s_h)S′′−s′′=21​(Sh​−sh​).

The FIFO-choice predicate. ccc consists of reals si,Si,ais_i,S_i,a_isi​,Si​,ai​ for i=1,…,ni=1,\dots,ni=1,…,n, and reals s0,S0s_0,S_0s0​,S0​. The predicate is the conjunction of:

  1. For each iii with Ki>0K_i>0Ki​>0 there exist reals sh,Sh,s′,S′s_h,S_h,s',S'sh​,Sh​,s′,S′ such that:
    • (sh,Sh)(s_h,S_h)(sh​,Sh​) is a canonical optimum for (ρi,Fi,53Ki)(\rho_i,F_i,\tfrac{5}{3}K_i)(ρi​,Fi​,35​Ki​);
    • (s′,S′)(s',S')(s′,S′) is a best half window of [sh,Sh][s_h,S_h][sh​,Sh​] for (ρi,Fi)(\rho_i,F_i)(ρi​,Fi​);
    • either (si,Si)=(sh,Sh)(s_i,S_i)=(s_h,S_h)(si​,Si​)=(sh​,Sh​) and Augi(sh,Sh)≤Augi(s′,S′)\mathrm{Aug}_i(s_h,S_h)\le\mathrm{Aug}_i(s',S')Augi​(sh​,Sh​)≤Augi​(s′,S′), or (si,Si)=(s′,S′)(s_i,S_i)=(s',S')(si​,Si​)=(s′,S′) and Augi(s′,S′)≤Augi(sh,Sh)\mathrm{Aug}_i(s',S')\le\mathrm{Aug}_i(s_h,S_h)Augi​(s′,S′)≤Augi​(sh​,Sh​);
    • Mρi(h,p;si,Si,ai)=Mˉρi(h,p;si,Si)\mathrm{M}_{\rho_i}(h,p;s_i,S_i,a_i)=\bar{\mathrm{M}}_{\rho_i}(h,p;s_i,S_i)Mρi​​(h,p;si​,Si​,ai​)=Mˉρi​​(h,p;si​,Si​), that is, aia_iai​ attains the infimum over aaa.
  2. For each iii with Ki=0K_i=0Ki​=0: si=Sis_i=S_isi​=Si​, Fi(Si)≤Fi(y)F_i(S_i)\le F_i(y)Fi​(Si​)≤Fi​(y) for every y∈Ry\in\mathbb{R}y∈R, and ai=Sia_i=S_iai​=Si​.
  3. s0≤S0s_0\le S_0s0​≤S0​.
  4. SSρΣ(f0,K0+Kmax⁡;s0,S0)=VρΣ(f0,K0+Kmax⁡)\mathrm{SS}_{\rho_\Sigma}(f_0,K_0+K_{\max};s_0,S_0)=V_{\rho_\Sigma}(f_0,K_0+K_{\max})SSρΣ​​(f0​,K0​+Kmax​;s0​,S0​)=VρΣ​​(f0​,K0​+Kmax​).

The fixed cost is 53Ki\tfrac{5}{3}K_i35​Ki​ in the canonical optimum, 000 in the half-window comparison, and KiK_iKi​ inside Augi\mathrm{Aug}_iAugi​. Under the standing assumptions each iii falls under exactly one of items 1 and 2.

The FIFO policy πN,x,cFIFO\pi^{\mathrm{FIFO}}_{N,x,c}πN,x,cFIFO​. It is deterministic. Its ordt(d)\mathrm{ord}_t(d)ordt​(d) and dispt,i(d)\mathrm{disp}_{t,i}(d)dispt,i​(d) are the period-ttt outputs of the state machine below, run on d0,…,dt−1d_0,\dots,d_{t-1}d0​,…,dt−1​.

The state consists of:

  • an on/off flag;
  • a free warehouse stock Wˉ\bar WWˉ;
  • retailer levels ℓi\ell_iℓi​;
  • scheduled arrivals SP(τ)\mathrm{SP}(\tau)SP(τ) at the warehouse and RPi(τ)\mathrm{RP}_i(\tau)RPi​(τ) at retailer iii, for every period τ\tauτ;
  • a queue (ordered list) of requests, each with a retailer, a size, an allocated amount and a shipped amount.

Initially the flag is off, Wˉ=W\bar W=WWˉ=W and ℓi=Ii\ell_i=I_iℓi​=Ii​. SP(τ)=ατ\mathrm{SP}(\tau)=\alpha_\tauSP(τ)=ατ​ for τ<L0\tau<L_0τ<L0​ and 000 otherwise, RPi(τ)=βi,τ\mathrm{RP}_i(\tau)=\beta_{i,\tau}RPi​(τ)=βi,τ​ for τ<Li\tau<L_iτ<Li​ and 000 otherwise, and the queue is empty.

In period ttt:

  1. Receive: Wˉ←Wˉ+SP(t)\bar W\leftarrow\bar W+\mathrm{SP}(t)Wˉ←Wˉ+SP(t) and ℓi←ℓi+RPi(t)\ell_i\leftarrow\ell_i+\mathrm{RP}_i(t)ℓi​←ℓi​+RPi​(t).
  2. If the flag is on, go to step 3. If it is off, check whether t+1≥Tpipe:=max⁡(L0,max⁡iLi)t+1\ge T_{\mathrm{pipe}}:=\max(L_0,\max_iL_i)t+1≥Tpipe​:=max(L0​,maxi​Li​) and ℓi≤Si\ell_i\le S_iℓi​≤Si​ for every iii.
    • If both hold, turn the flag on (it then stays on forever). Append, in increasing iii, a request of size Si−ℓiS_i-\ell_iSi​−ℓi​ for each iii with Si−ℓi>0S_i-\ell_i>0Si​−ℓi​>0, then continue with step 3.
    • Otherwise output ordt=0\mathrm{ord}_t=0ordt​=0 and dispt,i=0\mathrm{disp}_{t,i}=0dispt,i​=0, and go to step 5.
  3. Compute requests and the warehouse order from the state at the start of this step. Let ITi=∑k=1LiRPi(t+k)\mathrm{IT}_i=\sum_{k=1}^{L_i}\mathrm{RP}_i(t+k)ITi​=∑k=1Li​​RPi​(t+k) and IT0=∑k=1L0SP(t+k)\mathrm{IT}_0=\sum_{k=1}^{L_0}\mathrm{SP}(t+k)IT0​=∑k=1L0​​SP(t+k). Over retailer iii's queued requests, let Oi=∑(size−shipped)O_i=\sum(\text{size}-\text{shipped})Oi​=∑(size−shipped) and Ri=∑(allocated−shipped)R_i=\sum(\text{allocated}-\text{shipped})Ri​=∑(allocated−shipped).
    • Let p^i:=ℓi+ITi+Oi\hat p_i:=\ell_i+\mathrm{IT}_i+O_ip^​i​:=ℓi​+ITi​+Oi​. Each iii with p^i≤si\hat p_i\le s_ip^​i​≤si​ and Si−p^i>0S_i-\hat p_i>0Si​−p^​i​>0 gets a new request of size Si−p^iS_i-\hat p_iSi​−p^​i​, appended at the back of the queue in increasing iii.
    • Let P0:=Wˉ+∑iRi+IT0+∑i(ℓi+ITi−ai)P_0:=\bar W+\sum_iR_i+\mathrm{IT}_0+\sum_i(\ell_i+\mathrm{IT}_i-a_i)P0​:=Wˉ+∑i​Ri​+IT0​+∑i​(ℓi​+ITi​−ai​). The order is q0=S0−P0q_0=S_0-P_0q0​=S0​−P0​ if P0≤s0P_0\le s_0P0​≤s0​, and q0=0q_0=0q0​=0 otherwise. It is added to Wˉ\bar WWˉ at once if L0=0L_0=0L0​=0, and to SP(t+L0)\mathrm{SP}(t+L_0)SP(t+L0​) otherwise.
  4. FIFO allocation. Scan the queue from the front with w=Wˉw=\bar Ww=Wˉ. Each request receives min⁡(size−allocated, w)\min(\text{size}-\text{allocated},\,w)min(size−allocated,w), which is subtracted from www, and everything allocated but not yet shipped is shipped at once. Let DiD_iDi​ be the total shipped to retailer iii this period. Then:
    • set Wˉ=w\bar W=wWˉ=w and delete requests with shipped ≥\ge≥ size;
    • add DiD_iDi​ to ℓi\ell_iℓi​ at once if Li=0L_i=0Li​=0, and to RPi(t+Li)\mathrm{RP}_i(t+L_i)RPi​(t+Li​) otherwise;
    • output ordt=q0\mathrm{ord}_t=q_0ordt​=q0​ and dispt,i=Di\mathrm{disp}_{t,i}=D_idispt,i​=Di​.
  5. Demand: ℓi←ℓi−dt,i\ell_i\leftarrow\ell_i-d_{t,i}ℓi​←ℓi​−dt,i​.

The engine also has a per-retailer batching option. It is off for every retailer here, so request offsets, time stamps, the request counter and the offset rule (the zero rule) do not affect the outputs. The left side feeds only the output sequences ordt\mathrm{ord}_tordt​ and dispt,i\mathrm{disp}_{t,i}dispt,i​ into the generic formulas for WtW_tWt​, Ii,tI_{i,t}Ii,t​ and ctc_tct​ above. The engine's internal state does not enter the cost.

Edge cases and scope.

  • Role of 0<n0<n0<n. It excludes the network with no retailers. It makes Kmax⁡K_{\max}Kmax​ a maximum over a nonempty finite family, and it makes every clause quantified over retailers non-vacuous.

  • Constants. With m≥1m\ge1m≥1, the threshold 94+14m\tfrac{9}{4}+\tfrac{1}{4m}49​+4m1​ lies in (94,52](\tfrac{9}{4},\tfrac{5}{2}](49​,25​], equal to 52\tfrac{5}{2}25​ at m=1m=1m=1. Hence γ>94\gamma>\tfrac{9}{4}γ>49​, ofReal(γ)=γ\mathrm{ofReal}(\gamma)=\gammaofReal(γ)=γ and γ−1>54\gamma-1>\tfrac{5}{4}γ−1>45​.

  • Which γ\gammaγ are covered. mmm appears only in hypotheses. For a fixed network the statement covers every γ≥94+14m\gamma\ge\tfrac{9}{4}+\tfrac{1}{4m}γ≥49​+4m1​ with 1≤m≤min⁡iHi/h1\le m\le\min_iH_i/h1≤m≤mini​Hi​/h, subject also to (γ−1)K0≥Kmax⁡(\gamma-1)K_0\ge K_{\max}(γ−1)K0​≥Kmax​. If K0>0K_0>0K0​>0 that last condition reads γ≥1+Kmax⁡/K0\gamma\ge1+K_{\max}/K_0γ≥1+Kmax​/K0​. Networks with some Hi<hH_i<hHi​<h, or with p<hp<hp<h, are not covered.

  • K0=0K_0=0K0​=0. Then Kmax⁡≤0K_{\max}\le0Kmax​≤0, which together with Ki≥0K_i\ge0Ki​≥0 forces every Ki=0K_i=0Ki​=0.

  • Values in [0,∞][0,\infty][0,∞]. Both sides are extended nonnegative reals, and γ⋅∞=∞\gamma\cdot\infty=\inftyγ⋅∞=∞.

    • If OPT(N,x)=∞\mathrm{OPT}(N,x)=\inftyOPT(N,x)=∞, the inequality holds automatically.
    • If OPT(N,x)=0\mathrm{OPT}(N,x)=0OPT(N,x)=0, it asserts that the left side is 000.
    • A left side equal to ∞\infty∞ is compatible with the claim only when OPT(N,x)=∞\mathrm{OPT}(N,x)=\inftyOPT(N,x)=∞.
    • OPT\mathrm{OPT}OPT is not ∞\infty∞ by emptiness, since the class is nonempty for valid xxx. Whether it is finite depends on the data, and the statement does not say.
  • Truncation. Each ctc_tct​ enters as max⁡(ct,0)\max(c_t,0)max(ct​,0). For the FIFO policy, a negative ctc_tct​ could come only from h Wth\,W_thWt​ with Wt<0W_t<0Wt​<0, where WtW_tWt​ is the generic formula applied to the FIFO outputs. The statement neither excludes nor asserts this.

  • Status of the FIFO policy. The theorem does not state that the FIFO policy is feasible or measurable, or that it belongs to the class defining OPT\mathrm{OPT}OPT. It only compares two numbers. By construction its period-ttt outputs depend only on d0,…,dt−1d_0,\dots,d_{t-1}d0​,…,dt−1​, so the zero padding after TTT is immaterial on both sides. No measurability is assumed for it, which is where the lower-integral reading matters.

  • Attainment required by the predicate. The choice predicate requires exact attainment:

    • an optimal (s,S)(s,S)(s,S) pair for (ρΣ,f0,K0+Kmax⁡)(\rho_\Sigma,f_0,K_0+K_{\max})(ρΣ​,f0​,K0​+Kmax​);
    • for Ki>0K_i>0Ki​>0, a canonical optimum with finite VVV, an attained best half window, and an attained minimizing aia_iai​;
    • for Ki=0K_i=0Ki​=0, a minimizer of FiF_iFi​.

    The statement does not assert that such a ccc exists, and for a network admitting none it is vacuous. Equalities and inequalities between these averages are in [0,∞][0,\infty][0,∞], so item 4 and the aia_iai​ condition would also be met with both sides equal to ∞\infty∞.

  • Joint satisfiability. The hypotheses can all hold at once. Example data:

    • n=1n=1n=1, L0=L1=0L_0=L_1=0L0​=L1​=0, and μ\muμ the point mass at demand 111;
    • K0=1K_0=1K0​=1, K1=0K_1=0K1​=0, h=H1=p=1h=H_1=p=1h=H1​=p=1, m=1m=1m=1, γ=52\gamma=\tfrac{5}{2}γ=25​;
    • x=0x=0x=0 (all components zero);
    • ccc with s1=S1=a1=1s_1=S_1=a_1=1s1​=S1​=a1​=1 and (s0,S0)=(−1,0)(s_0,S_0)=(-1,0)(s0​,S0​)=(−1,0).

    Here F1(y)=∣y−1∣F_1(y)=|y-1|F1​(y)=∣y−1∣ and f0(y)=∣y∣f_0(y)=|y|f0​(y)=∣y∣, and both sides of item 4 equal 111.

Human review
  • Endorsed by Shuze Chen · Nov 17, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Ming Hu · Nov 17, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me