Lemma 3.3 — global lost-sales penalty comparison
ProvedLostSalesBalancing.DualBalancing.lemma_3_3inventorylost-salesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Run two nonnegative order sequences and against the same nonnegative demand path and initial pipeline. Let be the order periods for which at least one truncated position , , is at least . If , then
This global comparison bounds the marked lost-sales charges of by the comparison policy's charges across the horizon.
Formalization Note The paper names the comparison policy OPT. Here it is any nonnegative order sequence. The lost-sales penalty rates are nonnegative and non-increasing, as in the extension after the lemma on p. 14. The instance also contains ordering-cost monotonicity, which this lemma does not use. The sum on the right covers penalty periods .
Preamble
import Mathlib import Definitions.Def_LostSalesBalancing_DualBalancing_Model
Formal statement
namespace LostSalesBalancing.DualBalancing
open Finset
open scoped Classical
/-- Lemma 3.3: global amortization of marked lost-sales penalties. -/
theorem lemma_3_3 (I : LSInstance) (d QB QP : ℤ → ℝ)
(hd : ∀ j : ℤ, 1 ≤ j → j ≤ (I.T : ℤ) → 0 ≤ d j)
(hB : ∀ j : ℤ, 1 ≤ j → j ≤ (I.T : ℤ) → 0 ≤ QB j)
(hP : ∀ j : ℤ, 1 ≤ j → j ≤ (I.T : ℤ) → 0 ≤ QP j) :
(∑ t ∈ (Icc (1 : ℤ) ((I.T : ℤ) - I.L)).filter (fun t => ¬ InTH I d QB QP t),
lostLS I d QB t) ≤
∑ t ∈ Icc (1 : ℤ) ((I.T : ℤ) - I.L), lostLS I d QP t := by sorry
end LostSalesBalancing.DualBalancing
Source
Levi, Janakiraman, Nagarajan, A 2-Approximation Algorithm for Stochastic Inventory Control Models with Lost Sales, Math. Oper. Res. 33(2) (2008), accepted manuscript pp. 11–14, §3.2, Lemma 3.3 and remark
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.