pp. 852–853 — a maximizing pattern decides the pricing inequalities
ProvedGilmoreGomory61.CuttingStock.knapsack_maximum_testcolumn-generationcutting-stockknapsackp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Suppose all piece lengths are positive and the available stock length is nonnegative. For any multipliers there is a feasible nonnegative integer pattern attaining the maximum price
For any stock cost , a pattern satisfying both the length constraint and exists exactly when this maximizing pattern has price greater than . Thus one maximum calculation decides whether the paper's inequalities (6)–(7) are compatible.
Formalization Note Positive lengths make the feasible pattern set finite, and makes it nonempty. The page first says “positive integers” but immediately selects “nonnegative integers”; zero counts are allowed here. The maximum is compared through the extended-real value .
Preamble
import Mathlib import Definitions.Def_GilmoreGomory61_CuttingStock_Knapsack
Formal statement
namespace GilmoreGomory61.CuttingStock
/-- A maximum pattern tests the compatibility of (6) and (7), pp. 852–853. -/
theorem knapsack_maximum_test {m k : ℕ} (I : Instance m k)
(hℓ : ∀ i, 0 < I.ℓ i) (b : Fin m → ℝ) (L c : ℝ) (hL : 0 ≤ L) :
∃ aStar : Fin m → ℕ,
patLen I aStar ≤ L ∧
(∀ a : Fin m → ℕ, patLen I a ≤ L →
(∑ i, b i * (a i : ℝ)) ≤ ∑ i, b i * (aStar i : ℝ)) ∧
knapF I b m L = ((∑ i, b i * (aStar i : ℝ) : ℝ) : EReal) ∧
((∃ a : Fin m → ℕ, patLen I a ≤ L ∧
c < ∑ i, b i * (a i : ℝ)) ↔ c < ∑ i, b i * (aStar i : ℝ)) := by sorry
end GilmoreGomory61.CuttingStock
Source
Gilmore and Gomory, A linear programming approach to the cutting-stock problem, Oper. Res. 9(6) (1961), pp. 852–853, after (7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.