Lemma 6.2 —
ProvedLeviBalancing.TripleBalancing.lemma_6_2approximation-algorithminventory-controlp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-lot-sizing
Let TB be the triple-balancing policy for a stochastic lot-sizing model with conditional demand law , and let be the number of orders TB places. Then every feasible policy satisfies
The paper writes for an optimal policy OPT. The additive form is the same inequality whenever the expectations are finite, and it remains meaningful when ; the proof uses only the feasibility of OPT. Together with Lemma 6.1 it gives Theorem 6.1.
Formalization Note All quantities are in (lower Lebesgue integrals).
Preamble
import Mathlib import Definitions.Def_LeviBalancing_TripleBalancing_Model import Definitions.Def_LeviBalancing_TripleBalancing_Policy import Definitions.Def_LeviBalancing_TripleBalancing_TBPolicy open MeasureTheory ProbabilityTheory
Formal statement
namespace LeviBalancing.TripleBalancing
/-- Lemma 6.2 (p. 300), stated for every feasible policy `P` in place of an optimal policy and in
additive form: `E[𝒞(TB)] ≤ E[𝒞(P)] + 2K · E[N]`. -/
theorem lemma_6_2 {Ω : Type*} [MeasurableSpace Ω] (M : LotSizingModel Ω)
(I : ℕ → Kernel Ω (ℕ → ℝ)) (hI : M.IsCondDemandLaw I)
(TB : ℕ → Ω → ℝ) (hTB : IsTripleBalancing M I TB)
(P : ℕ → Ω → ℝ) (hP : IsFeasiblePolicy M P) :
expectedCost M TB ≤
expectedCost M P + 2 * ENNReal.ofReal M.K * ∫⁻ ω, (numOrders M TB ω : ENNReal) ∂M.μ := by sorry
end LeviBalancing.TripleBalancing
Source
Levi, Pál, Roundy & Shmoys, Approximation Algorithms for Stochastic Inventory Control Models, Math. Oper. Res. 32(2):284–302 (2007), DOI 10.1287/moor.1060.0205, p. 300 (PDF 17), Lemma 6.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.