Knapsack Method, Step (1), p. 867 — the vectors tested in Step (3) are generated in lexicographically decreasing order
ProvedCuttingStock63.Knapsack.tested_vectors_decreaseConsider the Knapsack Method with lengths and stock lengths . Let be a state reachable from the start at which Step (3) is about to be executed, and let be a later state of the same run (reached by one or more steps) at which Step (3) is again about to be executed. Then the vector of is lexicographically smaller than the vector of , and it satisfies .
So the method generates the vectors it tests in strictly decreasing lexicographic order, among the finitely many vectors that fit the longest stock length; this is the basis of the method's termination.
Formalization Note The page's definition of the lexicographic order ("for some , , , while ") omits vectors that differ in their first coefficient ( must range from 0); Mathlib's Pi.Lex order is used. The fit clause is stated for the later vector: the very first vector need not fit when (it is then the zero vector and the method stops at once).
import Mathlib import Definitions.Def_CuttingStock63_Knapsack_Problem import Definitions.Def_CuttingStock63_Knapsack_Method
namespace CuttingStock63.Knapsack
/-- Knapsack Method, Step (1), p. 867: the vectors tested in Step (3) are generated in
lexicographically decreasing order, and every one after the first satisfies L_1 ≥ λ·(α)_m. -/
theorem tested_vectors_decrease {m k : ℕ} (hk : 0 < k) (l b : Fin m → ℝ) (L c : Fin k → ℝ)
(hl : ∀ i, 0 < l i) (hL : StrictAnti L) (σ σ' : State m k)
(hσ : Reachable l b L c hk σ) (hu : σ.phase = .update)
(hσσ' : Relation.TransGen (Step l b L c) σ σ') (hu' : σ'.phase = .update) :
toLex σ'.a < toLex σ.a ∧ Fits l (L ⟨0, hk⟩) σ'.a := by sorry
end CuttingStock63.Knapsack
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.