Knapsack Method, Steps (2) and (7), pp. 867–868 — the greedy completion is the lexicographically largest feasible extension
ProvedCuttingStock63.Knapsack.greedy_lex_largestgreedyknapsacklexicographic-orderp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let be a capacity, and let be a prefix () with . Let be the greedy completion of Steps (2) and (7): for and
Then is an extension of , it satisfies , and every extension of with is lexicographically at most .
With this is the first claim of Step (2): the first vector of the method is the lexicographically largest -vector satisfying . With it is the claim behind Step (7).
Formalization Note The page writes "which satisfies " in Step (7); the prefix already satisfies that, and the intended condition is on the extension, , which is what is stated. The lexicographic order is Mathlib's Pi.Lex (toLex). Positive lengths are the paper's standing setting (demanded lengths).
Preamble
import Mathlib import Definitions.Def_CuttingStock63_Knapsack_Problem import Definitions.Def_CuttingStock63_Knapsack_Method
Formal statement
namespace CuttingStock63.Knapsack
/-- Steps (2) and (7), pp. 867–868: if the prefix (α)_s satisfies cap ≥ λ·(α)_s, the greedy
completion of Steps (2)/(7) is the lexicographically largest extension (α)_m of (α)_s that
satisfies cap ≥ λ·(α)_m. With `s = 0` this is Step (2)'s "lexicographically largest m-vector". -/
theorem greedy_lex_largest {m : ℕ} (l : Fin m → ℝ) (hl : ∀ i, 0 < l i) (cap : ℝ)
(a : Fin m → ℕ) (s : ℕ) (hs : s ≤ m) (hfit : lam l a s ≤ cap) :
IsExtension a (greedyFill l cap a s) s ∧ Fits l cap (greedyFill l cap a s) ∧
∀ a' : Fin m → ℕ, IsExtension a a' s → Fits l cap a' →
toLex a' ≤ toLex (greedyFill l cap a s) := by sorry
end CuttingStock63.Knapsack
Source
Gilmore & Gomory, A linear programming approach to the cutting stock problem—Part II, Opns. Res. 11 (1963), pp. 867–868, Knapsack Method, Step (2) and the paragraph before Step (5) (Step (7))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.