Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Consolidation upper bound: C(πcon(m))≤2J0(gmK0)+Bm∑iJi(ζmKi)C(\pi^{(m)}_{\rm con})\le2J_0(g_mK_0)+B_m\sum_iJ_i(\zeta_mK_i)C(πcon(m)​)≤2J0​(gm​K0​)+Bm​∑i​Ji​(ζm​Ki​)

Proved
OWMR.consolidation_upper_bound

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

approximation-algorithmsinventoryinventory-theoryoperations-researchstochastic-control

This is the cost bound for the consolidation policy that the source states after Theorem 2 (Section 6) and proves in Appendix C.

Let m≥1m\ge1m≥1, and set gm=γˉm/2=13/6+16/(57m)g_m=\bar\gamma_m/2=13/6+16/(57m)gm​=γˉ​m​/2=13/6+16/(57m), ζm=gm/(gm−1)\zeta_m=g_m/(g_m-1)ζm​=gm​/(gm​−1), and Bm=2(gm−1)B_m=2(g_m-1)Bm​=2(gm​−1). Consider an OWMR network that satisfies the standing assumptions, in which the retailer demands within each period are associated, Hi≥mhH_i\ge mhHi​≥mh for every retailer, and p≥hp\ge hp≥h. Then from every valid initial state xxx, for arbitrary nonnegative setup costs and all finite lead times, the deterministic consolidation policy πcon(m)\pi^{(m)}_{\rm con}πcon(m)​ of Definition 2 satisfies

C(πcon(m))≤2J0(gmK0)+Bm∑i=1nJi(ζmKi),C(\pi^{(m)}_{\rm con})\le2J_0(g_mK_0)+B_m\sum_{i=1}^nJ_i(\zeta_mK_i),C(πcon(m)​)≤2J0​(gm​K0​)+Bm​i=1∑n​Ji​(ζm​Ki​),

where CCC is the long-run average expected cost from xxx, and J0(k)J_0(k)J0​(k) and Ji(k)J_i(k)Ji​(k) are the optimal average costs of the supplier's and retailer iii's single-location problems with setup cost kkk.

The right side is twice the left side of the shared-cost lower bound (Proposition 3) at γ=gm\gamma=g_mγ=gm​, so this bound and Proposition 3 give Theorem 2 with the factor γˉm=2gm\bar\gamma_m=2g_mγˉ​m​=2gm​.

Formalization Note gmg_mgm​, ζm\zeta_mζm​, and BmB_mBm​ are conG m, conZeta m, and conB m; costs are extended nonnegative reals.

Preamble
import Definitions.Def_owmr_consolidation_policy

open scoped ENNReal
Formal statement
namespace OWMR
theorem consolidation_upper_bound {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
      ≤ 2 * N.J0 (conG m * N.K0) + ENNReal.ofReal (conB m) * ∑ i, N.J i (conZeta m * N.K 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 6, display following Theorem 2 (p. 28); proved in Appendix C as eq. (C.28) (p. E.20) for the uniform-offset policy and transferred to the consolidation policy in Steps 7 and 8 (Sections C.7 and C.8, pp. E.20-E.21).

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