Lemma 4.3, p. 294 — on every realization
ProvedLeviBalancing.DualBalancing.backlog_on_TPi_leapproximation-algorithmsinventory-controlp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix an instance, a realization of the demands , and two order sequences with nonnegative orders in periods . Let and be the resulting inventory positions after ordering, and let
be the periods in which holds at least as much inventory as . Then the marginal backlogging cost of over these periods is at most the total marginal backlogging cost of :
This is the backlogging half of the pathwise comparison behind Theorem 4.1.
Formalization Note As for Lemma 4.2, the statement holds for every realization and every pair of nonnegative order sequences, which strengthens the page's "for the dual-balancing policy and OPT, with probability one". is read as the marginal total of Eq. (4).
Preamble
import Mathlib import Definitions.Def_LeviBalancing_DualBalancing_Model open Finset
Formal statement
namespace LeviBalancing.DualBalancing
/-- Lemma 4.3, p. 294 (pathwise): for every demand realization and any two order processes with
nonnegative orders, the marginal backlogging cost of `B` over the periods
`𝒯_Π = {t : Y_t^B ≥ Y_t^P}` is at most the total marginal backlogging cost
`Π^P = ∑_{t=1}^{T−L} Π_t^P` of `P`. -/
theorem backlog_on_TPi_le (I : Instance) (d : ℤ → ℝ)
(hd : ∀ t : ℤ, 1 ≤ t → t ≤ (I.T : ℤ) → 0 ≤ d t) (qB qP : ℤ → ℝ)
(hqB : ∀ t : ℤ, 1 ≤ t → t ≤ (I.T : ℤ) → 0 ≤ qB t)
(hqP : ∀ t : ℤ, 1 ≤ t → t ≤ (I.T : ℤ) → 0 ≤ qP t) :
∑ t ∈ (Icc (1 : ℤ) ((I.T : ℤ) - I.L)).filter
(fun t => invPositionAfter I d qP t ≤ invPositionAfter I d qB t),
marginalBacklog I d qB t ≤
∑ t ∈ Icc (1 : ℤ) ((I.T : ℤ) - I.L), marginalBacklog I d qP t := by sorry
end LeviBalancing.DualBalancing
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. 294 (PDF p. 11), Lemma 4.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.