p. 853 — dynamic programming recursion for F_s
ProvedGilmoreGomory61.CuttingStock.knapsack_dp_recursioncutting-stockdynamic-programmingknapsackp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For the first piece lengths, with the new type indexed in zero-based notation, the knapsack value obeys
The finite range for is the paper's bound on the number of pieces of the new type. This relation is the dynamic programming computation used to test pricing for the available stock lengths.
Formalization Note The source uses one-based with new length ; Lean's new type has index . The statement requires positive lengths through this type. Earlier positive lengths are needed for the displayed finite range when negative capacities are permitted by the formal type. At , both sides are .
Preamble
import Mathlib import Definitions.Def_GilmoreGomory61_CuttingStock_Knapsack
Formal statement
namespace GilmoreGomory61.CuttingStock
/-- The Fₛ recursion and its finite range from p. 853. Earlier lengths must be positive too. -/
theorem knapsack_dp_recursion {m k : ℕ} (I : Instance m k)
(b : Fin m → ℝ) (s : ℕ) (hs : s < m)
(hℓ : ∀ i : Fin m, i.val ≤ s → 0 < I.ℓ i) (x : ℝ) :
knapF I b (s + 1) x =
⨆ r ∈ Finset.range (⌊x / I.ℓ ⟨s, hs⟩⌋₊ + 1),
(((r : ℝ) * b ⟨s, hs⟩ : ℝ) : EReal) +
knapF I b s (x - r * I.ℓ ⟨s, hs⟩) := by sorry
end GilmoreGomory61.CuttingStock
Source
Gilmore and Gomory, A linear programming approach to the cutting-stock problem, Oper. Res. 9(6) (1961), p. 853, recursion for F_{s+1}
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.