Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Roundy's 98 % approximation for a serial system: a nested powers-of-two policy within 1/(2ln⁡2)1/(\sqrt2\ln 2)1/(2​ln2) of the relaxed optimum

Proved
InventoryControl.roundy_serial

by naimengye · Sep 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsinventory-controllot-sizingmulti-echelonoperations-researchpowers-of-two

Roundy's 98 % approximation for a serial system, the capstone of Chapter 9.

A serial inventory system has NNN installations; installation iii produces item iii from one unit of item i+1i+1i+1, and item 1 faces a constant continuous demand d>0d > 0d>0. There are ordering costs Ai>0A_i > 0Ai​>0 and echelon holding costs ei>0e_i > 0ei​>0 at all stages, no shortages, zero lead-times, and constant batch quantities Qi>0Q_i > 0Qi​>0, with cost per time unit

C(Q)  =  ∑i=1N(eiQi2+AidQi).C(Q) \;=\; \sum_{i=1}^{N}\Big(e_i\frac{Q_i}{2} + A_i\frac{d}{Q_i}\Big).C(Q)=i=1∑N​(ei​2Qi​​+Ai​Qi​d​).

Let QrelQ^{\mathrm{rel}}Qrel minimize CCC subject to the relaxed nesting constraints Qi−1≤QiQ_{i-1} \le Q_iQi−1​≤Qi​ (Eq. 9.18). Then there are a basic quantity q>0q > 0q>0 and integers m1≤m2≤⋯≤mNm_1 \le m_2 \le \dots \le m_Nm1​≤m2​≤⋯≤mN​ such that the batch quantities Qi=2miqQ_i = 2^{m_i}qQi​=2mi​q satisfy Roundy's constraints (9.16), Qi=2kiQi−1Q_i = 2^{k_i}Q_{i-1}Qi​=2ki​Qi−1​ with ki≥0k_i \ge 0ki​≥0, and

C(2mq)  ≤  12 ln⁡2 C(Qrel)  ≈  1.0201 C(Qrel).C\big(2^{m}q\big) \;\le\; \frac{1}{\sqrt 2\,\ln 2}\,C\big(Q^{\mathrm{rel}}\big) \;\approx\; 1.0201\,C\big(Q^{\mathrm{rel}}\big).C(2mq)≤2​ln21​C(Qrel)≈1.0201C(Qrel).

Since every policy satisfying (9.16) satisfies (9.18), C(Qrel)C(Q^{\mathrm{rel}})C(Qrel) is a lower bound on the cost of any nested constant-batch policy, so Roundy's solution is within 2 % of the best such policy. The book adds that the same bound holds against the optimum over all policies, including those whose batch quantities vary over time, by the Lagrangean argument around Eq. (9.21); that stronger comparison class is not modelled here.

The proof combines the powers-of-two analysis of Sect. 7.1 with the structure of the relaxed optimum. The multipliers of the Lagrangean relaxation (9.19)-(9.20) turn the relaxed problem into NNN independent EOQ problems with modified holding costs ei′e_i'ei′​ whose solution is QrelQ^{\mathrm{rel}}Qrel; Proposition 7.2 applied to those independent problems gives a qqq whose rounding costs at most 1/(2ln⁡2)1/(\sqrt 2\ln 2)1/(2​ln2) times C′(Qrel)C'(Q^{\mathrm{rel}})C′(Qrel) under the modified costs, and complementary slackness (the multipliers vanish unless the constraint is tight, and equal quantities round to equal quantities) transfers the bound to the original costs. The rounding is monotone, so the result is nested.

Formalization Note The comparison class is stated explicitly: QrelQ^{\mathrm{rel}}Qrel is any minimizer over positive batch quantities satisfying (9.18), and the conclusion exhibits qqq and mmm. The constant is the exact 1/(2ln⁡2)1/(\sqrt 2\ln 2)1/(2​ln2) of Proposition 7.2, not a rounded 1.021.021.02.

Preamble
import Definitions.Def_InventoryControl_serial
Formal statement
namespace InventoryControl

theorem roundy_serial {N : ℕ} (A e : Fin N → ℝ) (d : ℝ) (hd : 0 < d)
    (hA : ∀ i, 0 < A i) (he : ∀ i, 0 < e i) (Qrel : Fin N → ℝ) (hpos : ∀ i, 0 < Qrel i)
    (hnest : SerialNested Qrel)
    (hopt : ∀ Q : Fin N → ℝ, (∀ i, 0 < Q i) → SerialNested Q →
      serialCost A e d Qrel ≤ serialCost A e d Q) :
    ∃ q : ℝ, 0 < q ∧ ∃ m : Fin N → ℤ,
      SerialPowerOfTwo (fun i => (2 : ℝ) ^ (m i) * q)
        ∧ serialCost A e d (fun i => (2 : ℝ) ^ (m i) * q)
            ≤ 1 / (Real.sqrt 2 * Real.log 2) * serialCost A e d Qrel := by sorry

end InventoryControl
Source
Sven Axsäter, Inventory Control, 3rd ed., Springer 2015, DOI 10.1007/978-3-319-15729-0, pp. 178-180, Sect. 9.2.2 'Roundy's 98% Approximation', Eq. (9.16)-(9.18), (9.22) and the paragraph after (9.22): 'We have feasible constant batch quantities and the cost increase compared to the optimal solution is at most 2 %, since it is at most 2 % compared to the lower bound (9.21)'; Roundy (1985, 1986)
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 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