Roundy's 98 % approximation for a serial system: a nested powers-of-two policy within of the relaxed optimum
ProvedInventoryControl.roundy_serialRoundy's 98 % approximation for a serial system, the capstone of Chapter 9.
A serial inventory system has installations; installation produces item from one unit of item , and item 1 faces a constant continuous demand . There are ordering costs and echelon holding costs at all stages, no shortages, zero lead-times, and constant batch quantities , with cost per time unit
Let minimize subject to the relaxed nesting constraints (Eq. 9.18). Then there are a basic quantity and integers such that the batch quantities satisfy Roundy's constraints (9.16), with , and
Since every policy satisfying (9.16) satisfies (9.18), 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 independent EOQ problems with modified holding costs whose solution is ; Proposition 7.2 applied to those independent problems gives a whose rounding costs at most times 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: is any minimizer over positive batch quantities satisfying (9.18), and the conclusion exhibits and . The constant is the exact of Proposition 7.2, not a rounded .
import Definitions.Def_InventoryControl_serial
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.