Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Arbitrary setup costs: C(πcon(m))≤γˉm OPTC(\pi^{(m)}_{\rm con})\le\bar\gamma_m\,\mathrm{OPT}C(πcon(m)​)≤γˉ​m​OPT (Theorem 2)

Proved
OWMR.arbitrary_setup_costs

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

approximation-algorithmsinventoryinventory-theoryoperations-researchstochastic-control

Let m≥1m\ge1m≥1. 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 (otherwise arbitrary), and h,Hi,p>0h,H_i,p>0h,Hi​,p>0. Suppose

  1. the retailer demands in each period are associated: Cov⁡(u(Dt),v(Dt))≥0\operatorname{Cov}(u(D_t),v(D_t))\ge0Cov(u(Dt​),v(Dt​))≥0 for all bounded, measurable, coordinatewise nondecreasing u,vu,vu,v,
  2. Hi≥mhH_i\ge mhHi​≥mh for every retailer iii, and
  3. p≥hp\ge hp≥h.

Then, for all finite supplier and retailer lead times and from every valid initial state, the deterministic consolidation policy πcon(m)\pi^{(m)}_{\rm con}πcon(m)​ of Definition 2 satisfies

C(πcon(m))≤γˉm OPT,γˉm=133+3257m.C(\pi^{(m)}_{\rm con})\le\bar\gamma_m\,\mathrm{OPT},\qquad\bar\gamma_m=\frac{13}{3}+\frac{32}{57m}.C(πcon(m)​)≤γˉ​m​OPT,γˉ​m​=313​+57m32​.

At m=1m=1m=1 the factor is 93/19<4.993/19<4.993/19<4.9, and it decreases to 13/313/313/3 as mmm grows. Unlike Theorem 1, the factor does not depend on the ratio of retailer to supplier setup costs.

Formalization Note The conclusion holds for every admissible choice in Definition 2 (IsConChoice N m c); πcon(m)\pi^{(m)}_{\rm con}πcon(m)​ depends on mmm through these choices. Costs take values in [0,∞][0,\infty][0,∞].

Preamble
import Definitions.Def_owmr_consolidation_policy

open scoped ENNReal
Formal statement
namespace OWMR
theorem arbitrary_setup_costs {n : ℕ} (hn : 0 < n) (N : Network n) (hN : N.Standing)
    (hA : N.Associated) (m : ℝ) (hm : 1 ≤ m) (hH : ∀ i, m * N.h ≤ N.H i) (hp : N.h ≤ N.p)
    (x : InitState n) (hx : x.Valid) (c : ConChoice n) (hc : IsConChoice N m c) :
    (conPolicy N x c).avgCost N x ≤ ENNReal.ofReal (13 / 3 + 32 / (57 * m)) * 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 6, Theorem 2 (Arbitrary Setup Costs), p. 28.
Read-back

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

Read-back: OWMR.arbitrary_setup_costs

What is asserted. Take any n∈Nn\in\mathbb Nn∈N with n>0n>0n>0. Take any network NNN with nnn retailers that satisfies the standing assumptions and the association property. Take any real m≥1m\ge 1m≥1 with m h≤Him\,h\le H_imh≤Hi​ for all iii, and suppose h≤ph\le ph≤p. Finally take any valid initial state xxx and any parameter bundle ccc that satisfies the choice predicate for (N,m)(N,m)(N,m). Then

CN,x(πN,x,ccon)  ≤  (133+3257 m)⋅OPT(N,x)in [0,∞].\mathcal C_{N,x}\big(\pi^{\rm con}_{N,x,c}\big)\;\le\;\Big(\frac{13}{3}+\frac{32}{57\,m}\Big)\cdot \mathrm{OPT}(N,x)\qquad\text{in }[0,\infty].CN,x​(πN,x,ccon​)≤(313​+57m32​)⋅OPT(N,x)in [0,∞].

The left side is the long-run average cost of the deterministic policy in §5. OPT(N,x)\mathrm{OPT}(N,x)OPT(N,x) (§2) is the infimum of the same cost over all admissible policies, randomized ones included. The constant γˉ(m)=133+3257m\bar\gamma(m)=\frac{13}{3}+\frac{32}{57m}γˉ​(m)=313​+57m32​ is a real number in (133,9319](\frac{13}{3},\frac{93}{19}](313​,1993​]. There is no division by zero because m≥1m\ge1m≥1, and the constant sits in [0,∞][0,\infty][0,∞] as itself. It is the same expression that defines the constants in §3.

1. Binders and hypotheses

  • n∈Nn\in\mathbb Nn∈N, with the hypothesis n>0n>0n>0. Retailers are indexed by i∈[n]={0,…,n−1}i\in[n]=\{0,\dots,n-1\}i∈[n]={0,…,n−1}.
  • NNN is a network with these fields:
    • lead times L0∈NL_0\in\mathbb NL0​∈N (supplier to warehouse) and Li∈NL_i\in\mathbb NLi​∈N (warehouse to retailer iii); zero is allowed;
    • a probability measure μ\muμ on R≥0n\mathbb R_{\ge0}^nR≥0n​, the law of one period's demand vector D=(Di)iD=(D_i)_iD=(Di​)i​;
    • real numbers K0K_0K0​ (setup cost per warehouse order), KiK_iKi​ (setup cost per shipment to iii), hhh (warehouse holding cost), HiH_iHi​ (retailer holding cost) and ppp (backorder cost).
  • Standing assumptions: for every iii, 0<Eμ[Di]<∞0<\mathbb E_\mu[D_i]<\infty0<Eμ​[Di​]<∞. Also K0≥0K_0\ge0K0​≥0, Ki≥0K_i\ge0Ki​≥0, h>0h>0h>0, Hi>0H_i>0Hi​>0 and p>0p>0p>0.
  • Association: for all Borel-measurable, bounded, coordinatewise nondecreasing u,v:R≥0n→Ru,v:\mathbb R_{\ge0}^n\to\mathbb Ru,v:R≥0n​→R,
∫u dμ⋅∫v dμ≤∫uv dμ,\int u\,d\mu\cdot\int v\,d\mu\le\int uv\,d\mu,∫udμ⋅∫vdμ≤∫uvdμ,

which says Covμ(u,v)≥0\mathrm{Cov}_\mu(u,v)\ge0Covμ​(u,v)≥0. Point masses and product measures (by Harris's inequality) satisfy this.

  • m∈Rm\in\mathbb Rm∈R with m≥1m\ge1m≥1, and m h≤Him\,h\le H_imh≤Hi​ for every iii. In particular every Hi≥hH_i\ge hHi​≥h, so mmm can be any value in [1,min⁡iHi/h][1,\min_i H_i/h][1,mini​Hi​/h].
  • h≤ph\le ph≤p.
  • xxx is the initial state:
    • W∈RW\in\mathbb RW∈R, the warehouse stock;
    • I∈RnI\in\mathbb R^nI∈Rn, the retailer net inventories;
    • a:N→Ra:\mathbb N\to\mathbb Ra:N→R, the warehouse pipeline: ata_tat​ arrives in period ttt, and is read only for t<L0t<L_0t<L0​;
    • b:[n]×N→Rb:[n]\times\mathbb N\to\mathbb Rb:[n]×N→R, the retailer pipelines: bi,tb_{i,t}bi,t​ arrives at iii in period ttt, and is read only for t<Lit<L_it<Li​.
  • Valid: W≥0W\ge0W≥0, at≥0a_t\ge0at​≥0 for all ttt, and bi,t≥0b_{i,t}\ge0bi,t​≥0 for all i,ti,ti,t. There is no constraint on III, so negative values (backlog) are allowed. Entries that are never read still have to be ≥0\ge0≥0.
  • ccc is a "consolidation choice" with these fields:
    • s,S∈Rns,S\in\mathbb R^ns,S∈Rn;
    • batch flags β∈{true,false}n\beta\in\{\text{true},\text{false}\}^nβ∈{true,false}n;
    • s0,S0∈Rs_0,S_0\in\mathbb Rs0​,S0​∈R;
    • a retailer i⋆∈[n]i^\star\in[n]i⋆∈[n];
    • offsets θ0∈Rn\theta^0\in\mathbb R^nθ0∈Rn;
    • a bijection e:N→Q∩(0,1)e:\mathbb N\to\mathbb Q\cap(0,1)e:N→Q∩(0,1), which enumerates the rationals in (0,1)(0,1)(0,1).
  • The hypothesis IsConChoice(N,m,c)\mathrm{IsConChoice}(N,m,c)IsConChoice(N,m,c), given in §4.

2. Cost functional and OPT

A policy on a randomization space (U,ν)(U,\nu)(U,ν) has two components, both functions of u∈Uu\in Uu∈U and of the whole demand path d=(d0,d1,… )d=(d_0,d_1,\dots)d=(d0​,d1​,…):

  • an order qt(u,d)∈Rq_t(u,d)\in\mathbb Rqt​(u,d)∈R;
  • dispatches rt,i(u,d)∈Rr_{t,i}(u,d)\in\mathbb Rrt,i​(u,d)∈R.

Arrivals are At=atA_t=a_tAt​=at​ for t<L0t<L_0t<L0​ and At=qt−L0A_t=q_{t-L_0}At​=qt−L0​​ otherwise, and Ai,t=bi,tA_{i,t}=b_{i,t}Ai,t​=bi,t​ for t<Lit<L_it<Li​ and Ai,t=rt−Li,iA_{i,t}=r_{t-L_i,i}Ai,t​=rt−Li​,i​ otherwise. The end-of-period stocks are

Wt=W+∑s=0t(As−∑irs,i),Ii,t=Ii+∑s=0t(Ai,s−ds,i),W_t=W+\sum_{s=0}^{t}\Big(A_s-\sum_i r_{s,i}\Big),\qquad I_{i,t}=I_i+\sum_{s=0}^{t}\big(A_{i,s}-d_{s,i}\big),Wt​=W+s=0∑t​(As​−i∑​rs,i​),Ii,t​=Ii​+s=0∑t​(Ai,s​−ds,i​),

and the period cost is

ct=K01{qt>0}+∑iKi1{rt,i>0}+h Wt+∑i(HiIi,t++p Ii,t−).c_t=K_0\mathbf 1\{q_t>0\}+\sum_iK_i\mathbf 1\{r_{t,i}>0\}+h\,W_t+\sum_i\big(H_iI_{i,t}^++p\,I_{i,t}^-\big).ct​=K0​1{qt​>0}+i∑​Ki​1{rt,i​>0}+hWt​+i∑​(Hi​Ii,t+​+pIi,t−​).

The long-run average cost is

CN,x(π,ν)=lim sup⁡T→∞1T∫∑t=0T−1max⁡(ct,0) d(ν⊗μ⊗T)∈[0,∞].\mathcal C_{N,x}(\pi,\nu)=\limsup_{T\to\infty}\frac1T\int\sum_{t=0}^{T-1}\max(c_t,0)\,d\big(\nu\otimes\mu^{\otimes T}\big)\in[0,\infty].CN,x​(π,ν)=T→∞limsup​T1​∫t=0∑T−1​max(ct​,0)d(ν⊗μ⊗T)∈[0,∞].

In this integral d0,…,dT−1d_0,\dots,d_{T-1}d0​,…,dT−1​ are i.i.d. μ\muμ and dt:=0d_t:=0dt​:=0 for t≥Tt\ge Tt≥T. The integral is a lower Lebesgue integral, so it is defined even when the integrand is not measurable. Each period cost is truncated below at 000.

OPT(N,x)∈[0,∞]\mathrm{OPT}(N,x)\in[0,\infty]OPT(N,x)∈[0,∞] is the infimum of CN,x(π,ν)\mathcal C_{N,x}(\pi,\nu)CN,x​(π,ν) over all measurable spaces UUU (any type in the base universe, any σ-algebra), all probability measures ν\nuν on UUU, and all policies that satisfy three conditions:

  • Nonanticipative: qtq_tqt​ and rtr_trt​ depend on ddd only through d0,…,dt−1d_0,\dots,d_{t-1}d0​,…,dt−1​.
  • Measurable: for each ttt, qtq_tqt​ and each rt,ir_{t,i}rt,i​ are measurable in (u,d)(u,d)(u,d) under the product σ-algebra.
  • Feasible for every uuu and every demand path, not just almost surely: qt≥0q_t\ge0qt​≥0, rt,i≥0r_{t,i}\ge0rt,i​≥0, and ∑irt,i≤Wt−1+At\sum_ir_{t,i}\le W_{t-1}+A_t∑i​rt,i​≤Wt−1​+At​ with W−1=WW_{-1}=WW−1​=W. This is equivalent to Wt≥0W_t\ge0Wt​≥0.

For feasible policies every ct≥0c_t\ge0ct​≥0, so the truncation never acts on the right side.

A deterministic policy is costed with a one-point UUU and ν\nuν the point mass. Nothing in the theorem assumes or claims that πcon\pi^{\rm con}πcon is feasible, nonanticipative or measurable. Its cost is simply the formula above applied to its orders and dispatches.

3. Auxiliary objects and constants

  • ρi\rho_iρi​ is the law of DiD_iDi​, and ρˉ\bar\rhoρˉ​ is the law of ∑iDi\sum_iD_i∑i​Di​; both live on R≥0\mathbb R_{\ge0}R≥0​.
  • Fi(y)=E[Hi(y−Σi)++p(Σi−y)+]F_i(y)=\mathbb E\big[H_i(y-\Sigma_i)^++p(\Sigma_i-y)^+\big]Fi​(y)=E[Hi​(y−Σi​)++p(Σi​−y)+], where Σi\Sigma_iΣi​ is a sum of Li+1L_i+1Li​+1 i.i.d. ρi\rho_iρi​ variables.
  • f0(y)=E[h(y−Σ0)++p(Σ0−y)+]f_0(y)=\mathbb E\big[h(y-\Sigma_0)^++p(\Sigma_0-y)^+\big]f0​(y)=E[h(y−Σ0​)++p(Σ0​−y)+], where Σ0\Sigma_0Σ0​ is a sum of L0L_0L0​ i.i.d. ρˉ\bar\rhoρˉ​ variables. If L0=0L_0=0L0​=0 this reduces to f0(y)=hy++py−f_0(y)=hy^++py^-f0​(y)=hy++py−.
  • FiF_iFi​ and f0f_0f0​ are Bochner integrals, so they would take the value 000 if the integrand were not integrable. Under the standing assumptions the integrands are integrable, and Fi,f0≥0F_i,f_0\ge0Fi​,f0​≥0.
  • Single-location optimum V(ρ,f,k)∈[0,∞]V(\rho,f,k)\in[0,\infty]V(ρ,f,k)∈[0,∞]. This is the infimum, over randomizations (U,ν)(U,\nu)(U,ν) and order rules qt(u,d)≥0q_t(u,d)\ge0qt​(u,d)≥0 that are nonanticipative and jointly measurable, of
lim sup⁡T1T E∑t<Tmax⁡(k1{qt>0}+f(yt),0),yt=∑s≤tqs−∑s<tds.\limsup_T\frac1T\,\mathbb E\sum_{t<T}\max\big(k\mathbf 1\{q_t>0\}+f(y_t),0\big),\qquad y_t=\sum_{s\le t}q_s-\sum_{s<t}d_s .Tlimsup​T1​Et<T∑​max(k1{qt​>0}+f(yt​),0),yt​=s≤t∑​qs​−s<t∑​ds​.

Here demands are i.i.d. ρ\rhoρ and the start is y=0y=0y=0. Write Ji(k)=V(ρi,Fi,k)J_i(k)=V(\rho_i,F_i,k)Ji​(k)=V(ρi​,Fi​,k).

  • (s,S)(s,S)(s,S) cost g(ρ,f,k,s,S)g(\rho,f,k,s,S)g(ρ,f,k,s,S). This is the same limsup average along the path defined by
    • y0−=Sy^-_0=Sy0−​=S;
    • yt+=Sy^+_t=Syt+​=S if yt−≤sy^-_t\le syt−​≤s, and yt+=yt−y^+_t=y^-_tyt+​=yt−​ otherwise;
    • yt+1−=yt+−dty^-_{t+1}=y^+_t-d_tyt+1−​=yt+​−dt​;
    • period cost k1{yt−≤s, yt−<S}+f(yt+)k\mathbf 1\{y^-_t\le s,\ y^-_t<S\}+f(y^+_t)k1{yt−​≤s, yt−​<S}+f(yt+​), truncated at 000.
  • Canonical optimum Can(ρ,f,k,s,S)\mathrm{Can}(\rho,f,k,s,S)Can(ρ,f,k,s,S). It holds when all of the following hold, comparing in [0,∞][0,\infty][0,∞]:
    • s<Ss<Ss<S;
    • g(ρ,f,k,s,S)=Vg(\rho,f,k,s,S)=Vg(ρ,f,k,s,S)=V;
    • f(s)=Vf(s)=Vf(s)=V;
    • f(S)≤Vf(S)\le Vf(S)≤V;
    • f(y)≤Vf(y)\le Vf(y)≤V for every y∈[s,S]y\in[s,S]y∈[s,S].
  • Best half window BHW(ρ,f,sh,Sh,s,S)\mathrm{BHW}(\rho,f,s^h,S^h,s,S)BHW(ρ,f,sh,Sh,s,S). It holds when sh≤s<S≤Shs^h\le s<S\le S^hsh≤s<S≤Sh, S−s=Sh−sh2S-s=\frac{S^h-s^h}2S−s=2Sh−sh​, and g(ρ,f,0,s,S)≤g(ρ,f,0,s′,S′)g(\rho,f,0,s,S)\le g(\rho,f,0,s',S')g(ρ,f,0,s,S)≤g(ρ,f,0,s′,S′) for every pair (s′,S′)(s',S')(s′,S′) meeting the same two constraints. The setup cost is 000 in this comparison.
  • Renewal function. Mρ(w)=∑k≥0ρ⊗k{z1+⋯+zk<w}∈[0,∞]M_\rho(w)=\sum_{k\ge0}\rho^{\otimes k}\{z_1+\dots+z_k<w\}\in[0,\infty]Mρ​(w)=∑k≥0​ρ⊗k{z1​+⋯+zk​<w}∈[0,∞]. The k=0k=0k=0 term equals 111 if w>0w>0w>0 and 000 otherwise.
  • Constants. G=γˉ(m)/2G=\bar\gamma(m)/2G=γˉ​(m)/2, ζ=GG−1\zeta=\frac{G}{G-1}ζ=G−1G​, B=2(G−1)B=2(G-1)B=2(G−1) and Υ=3ζ(1+1/m)4(4+ζ/m)\Upsilon=\frac{3\zeta(1+1/m)}{4(4+\zeta/m)}Υ=4(4+ζ/m)3ζ(1+1/m)​. For m≥1m\ge1m≥1 these satisfy G∈(136,9338]G\in(\frac{13}6,\frac{93}{38}]G∈(613​,3893​], ζ∈[9355,137)\zeta\in[\frac{93}{55},\frac{13}7)ζ∈[5593​,713​), B∈(73,5519]B\in(\frac73,\frac{55}{19}]B∈(37​,1955​] and Υ>0\Upsilon>0Υ>0, and every denominator is nonzero.

4. The choice predicate IsConChoice(N,m,c)\mathrm{IsConChoice}(N,m,c)IsConChoice(N,m,c)

The predicate is the conjunction of three clauses.

(R) Retailers. For every iii, set κi=ζKi\kappa_i=\zeta K_iκi​=ζKi​, αi=max⁡(inf⁡yFi(y)+Ki,0)\alpha_i=\max(\inf_yF_i(y)+K_i,0)αi​=max(infy​Fi​(y)+Ki​,0) and bi=B Ji(κi)∈[0,∞]b_i=B\,J_i(\kappa_i)\in[0,\infty]bi​=BJi​(κi​)∈[0,∞]. Exactly one of two cases applies.

  • If αi≤bi\alpha_i\le b_iαi​≤bi​: βi\beta_iβi​ is false, si=Sis_i=S_isi​=Si​, and SiS_iSi​ minimizes FiF_iFi​ over R\mathbb RR.
  • If bi<αib_i<\alpha_ibi​<αi​: βi\beta_iβi​ is true, and there exist reals sh,Shs^h,S^hsh,Sh with Can(ρi,Fi,κi,sh,Sh)\mathrm{Can}(\rho_i,F_i,\kappa_i,s^h,S^h)Can(ρi​,Fi​,κi​,sh,Sh). Define the ratio Ri=κi+/(Ji(κi) Mρi(Sh−sh))R_i=\kappa_i^+\big/\big(J_i(\kappa_i)\,M_{\rho_i}(S^h-s^h)\big)Ri​=κi+​/(Ji​(κi​)Mρi​​(Sh−sh)), computed in [0,∞][0,\infty][0,∞] (so x/0=∞x/0=\inftyx/0=∞ for x>0x>0x>0, 0/0=00/0=00/0=0, x/∞=0x/\infty=0x/∞=0).
    • If Ri≤ΥR_i\le\UpsilonRi​≤Υ, then BHW(ρi,Fi,sh,Sh,si,Si)\mathrm{BHW}(\rho_i,F_i,s^h,S^h,s_i,S_i)BHW(ρi​,Fi​,sh,Sh,si​,Si​).
    • If Ri>ΥR_i>\UpsilonRi​>Υ, then (si,Si)=(sh,Sh)(s_i,S_i)=(s^h,S^h)(si​,Si​)=(sh,Sh).

(W) Warehouse.

  • If K0>0K_0>0K0​>0: there exist sh,Shs^h,S^hsh,Sh with Can(ρˉ,f0,GK0,sh,Sh)\mathrm{Can}(\bar\rho,f_0,G K_0,s^h,S^h)Can(ρˉ​,f0​,GK0​,sh,Sh), and s0=sh+(−sh)+s_0=s^h+(-s^h)^+s0​=sh+(−sh)+, S0=Sh+(−sh)+S_0=S^h+(-s^h)^+S0​=Sh+(−sh)+. That is, the pair is shifted up so that s0=max⁡(sh,0)s_0=\max(s^h,0)s0​=max(sh,0).
  • If K0=0K_0=0K0​=0: s0=S0≥0s_0=S_0\ge0s0​=S0​≥0 and S0S_0S0​ minimizes f0f_0f0​.

(O) Offsets. 0<θi0<10<\theta^0_i<10<θi0​<1 for every iii.

The retailer i⋆i^\stari⋆ and the enumeration eee are not constrained at all.

How ccc depends on mmm. Only through four constants:

  • ζ(m)\zeta(m)ζ(m) scales the retailer setup costs used inside JiJ_iJi​ and Can\mathrm{Can}Can;
  • B(m)B(m)B(m) decides batch versus no batch;
  • Υ(m)\Upsilon(m)Υ(m) decides half window versus canonical window;
  • G(m)G(m)G(m) scales the warehouse setup cost inside Can\mathrm{Can}Can.

The policy itself takes no mmm; it depends on mmm only through ccc.

5. The policy πN,x,ccon\pi^{\rm con}_{N,x,c}πN,x,ccon​ (left side)

The policy is deterministic. Given a demand path ddd, it computes an internal state recursively:

  • σ0\sigma_0σ0​ is the initial state;
  • σt+1\sigma_{t+1}σt+1​ is the state left by Stept(σt)\mathrm{Step}_t(\sigma_t)Stept​(σt​), with IiI_iIi​ then reduced by dt,id_{t,i}dt,i​.

The order qtq_tqt​ and dispatches rt,ir_{t,i}rt,i​ are the outputs of Stept(σt)\mathrm{Step}_t(\sigma_t)Stept​(σt​), so they depend only on d0,…,dt−1d_0,\dots,d_{t-1}d0​,…,dt−1​. These outputs are costed by §2; the policy's own bookkeeping plays no part in the cost.

State. The state has these components:

  • a "running" flag;
  • the unallocated warehouse stock Wˉ\bar WWˉ;
  • the retailer inventories III;
  • scheduled arrivals α(τ)\alpha(\tau)α(τ) at the warehouse and αi(τ)\alpha_i(\tau)αi​(τ) at retailer iii, indexed by absolute period τ\tauτ;
  • a FIFO queue of requests, each with a retailer, size QQQ, allocated amount, shipped amount, offset θ\thetaθ and creation period;
  • a counter of requests created in phase A.

Initially the flag is off, Wˉ=W\bar W=WWˉ=W and III is the initial vector. α(τ)=aτ\alpha(\tau)=a_\tauα(τ)=aτ​ for τ<L0\tau<L_0τ<L0​ and 000 otherwise, αi(τ)=bi,τ\alpha_i(\tau)=b_{i,\tau}αi​(τ)=bi,τ​ for τ<Li\tau<L_iτ<Li​ and 000 otherwise, the queue is empty and the counter is 000.

Positions. For a state at period ttt:

  • physi=Ii+∑k=1Liαi(t+k)\mathrm{phys}_i=I_i+\sum_{k=1}^{L_i}\alpha_i(t+k)physi​=Ii​+∑k=1Li​​αi​(t+k);
  • unali\mathrm{unal}_iunali​ is the sum of Q−Q-Q−alloc over iii's queued requests;
  • resi\mathrm{res}_iresi​ is the sum of alloc−-−shipped over iii's queued requests;
  • y^i=physi+unali+resi\hat y_i=\mathrm{phys}_i+\mathrm{unal}_i+\mathrm{res}_iy^​i​=physi​+unali​+resi​.

Stept\mathrm{Step}_tStept​. First receive arrivals: Wˉ←Wˉ+α(t)\bar W\leftarrow\bar W+\alpha(t)Wˉ←Wˉ+α(t) and Ii←Ii+αi(t)I_i\leftarrow I_i+\alpha_i(t)Ii​←Ii​+αi​(t). Let Tp=max⁡(L0,max⁡iLi)T_p=\max(L_0,\max_iL_i)Tp​=max(L0​,maxi​Li​) and τ⋆=max⁡(Tp−1,0)\tau^\star=\max(T_p-1,0)τ⋆=max(Tp​−1,0) (natural-number subtraction). Then take the first branch that applies:

  1. If the flag is on, do a regular step.
  2. Else if t=τ⋆t=\tau^\start=τ⋆, ship all of Wˉ\bar WWˉ to i⋆i^\stari⋆, set Wˉ=0\bar W=0Wˉ=0, and order 000.
  3. Else if t>τ⋆t>\tau^\start>τ⋆, t≥τ⋆+Li⋆t\ge\tau^\star+L_{i^\star}t≥τ⋆+Li⋆​, and Ii≤SiI_i\le S_iIi​≤Si​ for all iii: turn the flag on. For each iii with Si−Ii>0S_i-I_i>0Si​−Ii​>0, in index order, append a request of size Si−IiS_i-I_iSi​−Ii​, offset θi0\theta^0_iθi0​, created at ttt; these requests do not increase the counter. Then do a regular step.
  4. Otherwise order 000 and dispatch 000.

Regular step, phase A. All quantities are computed on the post-receipt state.

  • Each retailer with y^i≤si\hat y_i\le s_iy^​i​≤si​ and Qi:=Si−y^i>0Q_i:=S_i-\hat y_i>0Qi​:=Si​−y^​i​>0 creates a request of size QiQ_iQi​.
  • The warehouse position is
y0=Wˉ+∑iresi+∑k=1L0α(t+k)+∑i(physi−Si).y_0=\bar W+\sum_i\mathrm{res}_i+\sum_{k=1}^{L_0}\alpha(t+k)+\sum_i(\mathrm{phys}_i-S_i).y0​=Wˉ+i∑​resi​+k=1∑L0​​α(t+k)+i∑​(physi​−Si​).
  • The warehouse orders q=S0−y0q=S_0-y_0q=S0​−y0​ if y0≤s0y_0\le s_0y0​≤s0​, and q=0q=0q=0 otherwise. The order is booked to arrive at t+L0t+L_0t+L0​, or added to Wˉ\bar WWˉ at once if L0=0L_0=0L0​=0.
  • Each new request gets offset 000 if βi\beta_iβi​ is false. If βi\beta_iβi​ is true it gets the offset from the rule below, evaluated on the provisional state (new requests and the order already booked).

Regular step, phase B. Go through the queue in order, starting with w=Wˉw=\bar Ww=Wˉ. Give each request a=min⁡(Q−alloc,w)a=\min(Q-\text{alloc},w)a=min(Q−alloc,w) and set w←w−aw\leftarrow w-aw←w−a.

  • If the request's retailer has β\betaβ false, ship all of its allocated but unshipped stock.
  • If β\betaβ is true, ship that stock only when the allocation moves from prev to new in one of three ways, and otherwise keep it reserved:
    • prev<34Qθ≤new\text{prev}<\frac34Q\theta\le\text{new}prev<43​Qθ≤new; or
    • θ<13\theta<\frac13θ<31​ and prev<34Q(1+θ)≤new\text{prev}<\frac34Q(1+\theta)\le\text{new}prev<43​Q(1+θ)≤new; or
    • prev<Q=new\text{prev}<Q=\text{new}prev<Q=new.

After the pass, Wˉ←w\bar W\leftarrow wWˉ←w and fully shipped requests are dropped. A shipment to iii is added to IiI_iIi​ at once if Li=0L_i=0Li​=0, and booked at t+Lit+L_it+Li​ otherwise. The outputs are qt=qq_t=qqt​=q and rt,i=r_{t,i}=rt,i​= the total shipped to iii.

Offset rule. It applies to a new batch request of retailer iii with size QQQ at period ttt. Let j≥1j\ge1j≥1 be the counter before this period plus iii's 1-based position among the retailers requesting in this period. Then θ=e(k∗)\theta=e(k^*)θ=e(k∗), where k∗k^*k∗ is the least kkk with

z(e(k))<zˉ+2−j,zˉ=∫01z(θ) dθ,z(e(k))<\bar z+2^{-j},\qquad \bar z=\int_0^1z(\theta)\,d\theta,z(e(k))<zˉ+2−j,zˉ=∫01​z(θ)dθ,

and θ=12\theta=\frac12θ=21​ if no such kkk exists. Here z(θ)∈[0,∞]z(\theta)\in[0,\infty]z(θ)∈[0,∞] is the expectation, over L0L_0L0​ fresh i.i.d. demand vectors drawn from μ\muμ, of the proxy

(3Ki if θ<13, else 2Ki)+(h+p)∑k=0L0(Ak−shk(θ)−Δk)+.\big(3K_i\text{ if }\theta<\tfrac13,\ \text{else }2K_i\big)+(h+p)\sum_{k=0}^{L_0}\big(A_k-\mathrm{sh}_k(\theta)-\Delta_k\big)^+ .(3Ki​ if θ<31​, else 2Ki​)+(h+p)k=0∑L0​​(Ak​−shk​(θ)−Δk​)+.

The proxy is computed by re-running regular steps from the provisional state through periods t,…,t+L0t,\dots,t+L_0t,…,t+L0​, with batching switched off for every retailer and the fresh demands. Its terms are:

  • AkA_kAk​ is the allocation, after phase B of period t+kt+kt+k, of the first queued request of retailer iii created at ttt, or QQQ if no such request remains;
  • Δk=∑i′(Si′−y^i′)\Delta_k=\sum_{i'}(S_{i'}-\hat y_{i'})Δk​=∑i′​(Si′​−y^​i′​), evaluated after phase A of period t+kt+kt+k;
  • shk(θ)=Ak\mathrm{sh}_k(\theta)=A_kshk​(θ)=Ak​ if the threshold test with offset θ\thetaθ passes from Ak−1A_{k-1}Ak−1​ to AkA_kAk​ (taking A−1=0A_{-1}=0A−1​=0), and shk−1(θ)\mathrm{sh}_{k-1}(\theta)shk−1​(θ) otherwise (taking sh−1=0\mathrm{sh}_{-1}=0sh−1​=0).

6. Edge cases

  • n>0n>0n>0. Any ccc already contains i⋆∈[n]i^\star\in[n]i⋆∈[n], so the existence of ccc forces n≥1n\ge1n≥1 on its own. With n≥1n\ge1n≥1, max⁡iLi\max_iL_imaxi​Li​ is a genuine maximum.

  • Values in [0,∞][0,\infty][0,∞]. Both sides lie in [0,∞][0,\infty][0,∞], and 0⋅∞=00\cdot\infty=00⋅∞=0. Because γˉ(m)∈(0,∞)\bar\gamma(m)\in(0,\infty)γˉ​(m)∈(0,∞):

    • if OPT=∞\mathrm{OPT}=\inftyOPT=∞, the claim holds trivially;
    • if OPT=0\mathrm{OPT}=0OPT=0, the claim says the left side equals 000.
  • OPT=0\mathrm{OPT}=0OPT=0 is not excluded. Take μ\muμ a point mass at a∈(0,∞)na\in(0,\infty)^na∈(0,∞)n, K0=Ki=0K_0=K_i=0K0​=Ki​=0, L0=Li=0L_0=L_i=0L0​=Li​=0, W=0W=0W=0, I=0I=0I=0, m=1m=1m=1, Hi≥hH_i\ge hHi​≥h and p≥hp\ge hp≥h. Ordering ∑iai\sum_ia_i∑i​ai​ and dispatching aia_iai​ every period is then feasible at zero cost. A valid ccc exists in this instance: β≡\beta\equivβ≡ false, si=Si=ais_i=S_i=a_isi​=Si​=ai​, s0=S0=0s_0=S_0=0s0​=S0​=0.

  • No finiteness claim. No hypothesis bounds the left side, and the theorem asserts only the inequality.

  • Every admissible ccc. The claim holds for every ccc satisfying the predicate: any choice among minimizers, canonical pairs or best windows, any i⋆i^\stari⋆, any enumeration eee, any θ0∈(0,1)n\theta^0\in(0,1)^nθ0∈(0,1)n.

  • Existence is assumed, not proved. The predicate requires several objects to exist:

    • minimizers of FiF_iFi​ and of f0f_0f0​ (the latter with S0≥0S_0\ge0S0​≥0);
    • canonical pairs satisfying the exact equalities f(s)=Vf(s)=Vf(s)=V and g=Vg=Vg=V, which is possible only if V<∞V<\inftyV<∞;
    • a minimizing half window.

    The theorem does not assert that these exist. For any (N,m)(N,m)(N,m) where no ccc satisfies the predicate, the statement is vacuous for that instance.

  • Range of mmm. Instances with min⁡iHi<h\min_iH_i<hmini​Hi​<h are excluded. A larger admissible mmm gives a smaller constant but changes which ccc are admissible.

  • Zero lead times. These are allowed. If Tp=0T_p=0Tp​=0, then τ⋆=0\tau^\star=0τ⋆=0 and the ship-everything-to-i⋆i^\stari⋆ branch runs at t=0t=0t=0.

  • limsup on both sides. Both average costs use limsup, and OPT is an infimum of limsups.

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