Knapsack Method, Step (4), p. 867 — the lexicographic predecessor of (α)_m extends (α¹)_s
ProvedCuttingStock63.Knapsack.lex_predecessorknapsacklexicographic-orderp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let satisfy . Let be the largest index with and let be with its -th coefficient replaced by . Then:
- among the vectors of nonnegative integers with that are lexicographically smaller than there is a lexicographically largest one;
- every such lexicographically largest vector is an extension of .
This is why Step (5) starts by replacing by : the next candidate in the lexicographic enumeration agrees with before position and has in position .
Formalization Note The page says "the lexicographically largest -vector lexicographically smaller than "; the -vectors are read as those satisfying the length constraint, as in the sentence defining the sequence of vectors (without the constraint the coordinates after are unbounded and no largest vector exists). The paper's 1-based is i.val + 1 for the 0-based index i.
Preamble
import Mathlib import Definitions.Def_CuttingStock63_Knapsack_Problem
Formal statement
namespace CuttingStock63.Knapsack
/-- Step (4), p. 867: let (α)_m satisfy cap ≥ λ·(α)_m and let `i` (the paper's s, 0-based) be the
largest index with a_i ≠ 0. Among the m-vectors satisfying the length constraint and
lexicographically smaller than (α)_m there is a lexicographically largest one, and every such
largest vector is an extension of (α¹)_s, which differs from (α)_s only in having a_s − 1 as its
s-th coefficient. -/
theorem lex_predecessor {m : ℕ} (l : Fin m → ℝ) (hl : ∀ i, 0 < l i) (cap : ℝ)
(a : Fin m → ℕ) (hfit : Fits l cap a) (i : Fin m) (hi : a i ≠ 0)
(hmax : ∀ i' : Fin m, i < i' → a i' = 0) :
(∃ g : Fin m → ℕ, Fits l cap g ∧ toLex g < toLex a ∧
∀ a' : Fin m → ℕ, Fits l cap a' → toLex a' < toLex a → toLex a' ≤ toLex g) ∧
∀ g : Fin m → ℕ, Fits l cap g → toLex g < toLex a →
(∀ a' : Fin m → ℕ, Fits l cap a' → toLex a' < toLex a → toLex a' ≤ toLex g) →
IsExtension (decrAt a (i.val + 1)) g (i.val + 1) := by sorry
end CuttingStock63.Knapsack
Source
Gilmore & Gomory, A linear programming approach to the cutting stock problem—Part II, Opns. Res. 11 (1963), p. 867, Knapsack Method, Step (4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.