Theorem 6.1 — the triple-balancing policy is a 3-approximation for stochastic lot-sizing
ProvedLeviBalancing.TripleBalancing.triple_balancing_three_approximationConsider an instance of the stochastic lot-sizing problem: periods, a fixed ordering cost , holding costs , backlogging penalties , an initial inventory level , and nonnegative, arbitrarily correlated demands with conditional demand law , where the demand of each period is known at the beginning of that period. Let TB be the triple-balancing policy. Then for every feasible (nonanticipatory) policy ,
In particular the expected cost of the triple-balancing policy is at most three times the expected cost of an optimal policy. This is the paper's constant-factor guarantee for the stochastic lot-sizing problem, where computing an optimal policy is intractable in general.
Formalization Note The paper compares TB with "an optimal policy"; the statement is for every feasible policy, which implies the paper's whenever an optimal policy exists and needs no existence assumption. Expected costs are lower Lebesgue integrals in . The statement quantifies over every policy satisfying the triple-balancing rules; such a policy exists when (separate theorem).
import Mathlib import Definitions.Def_LeviBalancing_TripleBalancing_Model import Definitions.Def_LeviBalancing_TripleBalancing_Policy import Definitions.Def_LeviBalancing_TripleBalancing_TBPolicy open MeasureTheory ProbabilityTheory
namespace LeviBalancing.TripleBalancing
/-- Theorem 6.1 (p. 301): the expected cost of the triple-balancing policy is at most three times
the expected cost of any feasible policy (in particular, of an optimal one). -/
theorem triple_balancing_three_approximation {Ω : Type*} [MeasurableSpace Ω]
(M : LotSizingModel Ω) (I : ℕ → Kernel Ω (ℕ → ℝ)) (hI : M.IsCondDemandLaw I)
(TB : ℕ → Ω → ℝ) (hTB : IsTripleBalancing M I TB)
(P : ℕ → Ω → ℝ) (hP : IsFeasiblePolicy M P) :
expectedCost M TB ≤ 3 * expectedCost M P := by sorry
end LeviBalancing.TripleBalancing
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.