Section 4 — greedy forward D′ solution is optimal
ProvedWagelmansELS.DualGreedy.greedy_forward_optimalgreedy-algorithmlinear-optimizationlot-sizingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
For an economic lot-sizing instance with nonnegative demands and setup costs and unrestricted marginal costs, let be any vector satisfying the greedy forward rule. Then satisfies every constraint of Program D′, each prefix objective equals the forward lot-sizing cost,
and no feasible vector has a larger full-horizon objective:
Thus every greedy forward choice, including arbitrary values at zero-demand periods, is optimal for D′. The identification of with the primal optimum follows the paper's zero-inventory property and is outside this formal statement.
Preamble
import Mathlib import Definitions.Def_WagelmansELS_DualGreedy_Greedy
Formal statement
namespace WagelmansELS.DualGreedy
theorem greedy_forward_optimal (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 ∧
(∀ j, 1 ≤ j → j ≤ P.n → objective P v j = F P j) ∧
(∀ u, IsFeasible P u → objective P u P.n ≤ objective P v P.n) := by sorry
end WagelmansELS.DualGreedy
Source
Wagelmans, Van Hoesel and Kolen, Economic Lot Sizing, Oper. Res. 40 Supp. 1 (1992), p. S153, Section 4, paragraphs from “To prove optimality” through “yields the desired result”
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.