Section 4 — greedy dual values decrease across positive demands
ProvedWagelmansELS.DualGreedy.greedy_forward_monotonegreedy-algorithmlot-sizingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let satisfy the greedy forward rule with nonnegative demands and setup costs. For any positive-demand periods ,
The paper states the result first for consecutive periods with nonzero demand, then observes that the dual values at zero-demand periods can be assigned freely. The formal statement skips those periods, so it holds for every allowed assignment of their values.
Preamble
import Mathlib import Definitions.Def_WagelmansELS_DualGreedy_Greedy
Formal statement
namespace WagelmansELS.DualGreedy
theorem greedy_forward_monotone (P : Instance) (v : ℕ → ℝ)
(hd : ∀ t, 1 ≤ t → t ≤ P.n → 0 ≤ P.d t)
(hf : ∀ i, 1 ≤ i → i ≤ P.n → 0 ≤ P.f i)
(hv : IsGreedyForward P v)
(t j : ℕ) (ht : 1 ≤ t) (htj : t < j) (hjn : j ≤ P.n)
(hdt : 0 < P.d t) (hdj : 0 < P.d j) : v j ≤ v t := by sorry
end WagelmansELS.DualGreedy
Source
Wagelmans, Van Hoesel and Kolen, Economic Lot Sizing, Oper. Res. 40 Supp. 1 (1992), p. S153, Section 4, “if d_j ≠ 0 and d_{j+1} ≠ 0, then v_j ≥ v_{j+1}” and the following zero-demand sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.