Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Physical upper bound for πFIFO\pi_{\rm FIFO}πFIFO​ (Proposition 2)

Proved
OWMR.fifo_physical_upper_bound

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

approximation-algorithmsinventoryinventory-theoryoperations-researchstochastic-control

This is the physical upper bound for the deterministic FIFO policy (Proposition 2 of the source).

Consider an OWMR network with n≥1n\ge1n≥1 retailers that satisfies the standing assumptions, a valid initial state xxx, and admissible choices for the FIFO policy πFIFO\pi_{\rm FIFO}πFIFO​ of Definition 1 (canonical optima, best half windows, mirror centers aia_iai​, and the supplier pair (s0,S0)(s_0,S_0)(s0​,S0​)). Let (si,Si)(s_i,S_i)(si​,Si​) be the (s,S)(s,S)(s,S) pair that retailer iii operates, and let

Li=Ci(si,Si)+Mi(si,Si)\mathcal L_i=\mathcal C_i(s_i,S_i)+\mathcal M_i(s_i,S_i)Li​=Ci​(si​,Si​)+Mi​(si​,Si​)

be its augmented cost: the long-run average cost Ci\mathcal C_iCi​ of the (si,Si)(s_i,S_i)(si​,Si​) policy in retailer iii's single-location problem with actual setup cost KiK_iKi​ and holding and backlog cost FiF_iFi​, plus its mirror cost Mi\mathcal M_iMi​, the minimum over centers aaa of the long-run average of ϕ(a−P^i,t)\phi(a-\widehat P_{i,t})ϕ(a−Pi,t​), where ϕ(y)=hy++py−\phi(y)=hy^++py^-ϕ(y)=hy++py− and P^i,t\widehat P_{i,t}Pi,t​ is the retailer's position including outstanding requests. Then

C(πFIFO)≤J0(K0+Kmax⁡)+∑i=1nLi,C(\pi_{\rm FIFO})\le J_0(K_0+K_{\max})+\sum_{i=1}^n\mathcal L_i,C(πFIFO​)≤J0​(K0​+Kmax​)+i=1∑n​Li​,

where C(πFIFO)C(\pi_{\rm FIFO})C(πFIFO​) is the long-run average expected cost from xxx, Kmax⁡=max⁡iKiK_{\max}=\max_iK_iKmax​=maxi​Ki​, and J0(k)J_0(k)J0​(k) is the optimal average cost of the supplier's single-location problem with aggregate demand, cost fL0f_{L_0}fL0​​, and setup cost kkk.

The supplier is charged one single-location problem at the inflated setup cost K0+Kmax⁡K_0+K_{\max}K0​+Kmax​, which pays for continuation shipments, and each retailer is charged its own augmented cost. With the retailer comparison and the shared-cost lower bound (Proposition 3), this bound yields Theorem 1.

Formalization Note Costs are extended nonnegative reals. The augmented cost is N.augCost i (c.s i) (c.S i), the sum of ssAvgCost at setup cost KiK_iKi​ and mirrorCost; a retailer with Ki=0K_i=0Ki​=0 uses base stock (si=Sis_i=S_isi​=Si​).

Preamble
import Definitions.Def_owmr_fifo_policy

open scoped ENNReal
Formal statement
namespace OWMR
theorem fifo_physical_upper_bound {n : ℕ} (hn : 0 < n) (N : Network n) (hN : N.Standing)
    (x : InitState n) (hx : x.Valid) (c : FIFOChoice n) (hc : IsFIFOChoice N c) :
    (fifoPolicy N x c).avgCost N x ≤ N.J0 (N.K0 + N.Kmax) + ∑ i, N.augCost i (c.s i) (c.S i) := 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 5.2, Proposition 2 (Physical Upper Bound), eq. (27), p. 23; proved in Appendix B (p. E.4).

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