Section 4 — greedy forward values satisfy D′
ProvedWagelmansELS.DualGreedy.greedy_forward_feasiblegreedy-algorithmlot-sizingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let demands and setup costs be nonnegative and marginal costs unrestricted. Every vector satisfying the greedy forward rule obeys all constraints of Program D′:
This establishes feasibility before comparing the greedy objective with the lot-sizing cost. Zero-demand coordinates may have arbitrary values.
Preamble
import Mathlib import Definitions.Def_WagelmansELS_DualGreedy_Greedy
Formal statement
namespace WagelmansELS.DualGreedy
theorem greedy_forward_feasible (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) : IsFeasible P v := by sorry
end WagelmansELS.DualGreedy
Source
Wagelmans, Van Hoesel and Kolen, Economic Lot Sizing, Oper. Res. 40 Supp. 1 (1992), p. S153, Section 4, “The solution constructed in this greedy forward way is clearly feasible”
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.