Knapsack Method, p. 868 — after a failed test in Step (5), no vector before the successor of Step (6) improves M_j
ProvedCuttingStock63.Knapsack.successor_boundLet and be ordered by density, , with the slack item , . Let , let be a prefix, and let , be a stock length and its current maximum such that the inequality of the test of Step (5) fails:
Then every vector of nonnegative integers with for , and satisfies .
These are exactly the vectors lexicographically between and the successor computed in Step (6), the lexicographically largest -vector smaller than ; so after a failed test the method may jump to that successor without missing an improvement of .
Formalization Note This is the corrected form of the page's claim. The page concludes from "the failure of the necessary condition in (5)" for every ; but the test of Step (5) for also requires , and when that part fails for a shorter stock length, smaller values of may still fit and improve . The statement therefore assumes the failure of the inequality itself (which is what the test establishes for every whose length accommodates the prefix). Nonnegative prices are a disclosed hypothesis, as for the relaxation bound.
import Mathlib import Definitions.Def_CuttingStock63_Knapsack_Problem
namespace CuttingStock63.Knapsack
/-- Knapsack Method, paragraph before Step (5), p. 868 (the successor of Step (6)), in corrected
form: if the inequality of the test of Step (5) fails for a stock length L with current value M at
the prefix (α)_s, that is (L − λ·(α)_s) b_{s+1} ≤ (M − β·(α)_s) l_{s+1}, then no vector a' that
agrees with (α)_s in its first s − 1 coefficients, has a'_s ≤ a_s and satisfies L ≥ λ·(α')_m
improves M. Hence nothing between (α)_s and the successor computed in Step (6) can improve M. -/
theorem successor_bound {m : ℕ} (l b : Fin m → ℝ) (hl : ∀ i, 0 < l i) (hb : ∀ i, 0 ≤ b i)
(hdens : ∀ i i' : Fin m, i ≤ i' → b i' / l i' ≤ b i / l i) (L M : ℝ) (a : Fin m → ℕ)
(s : ℕ) (hs1 : 1 ≤ s) (hsm : s ≤ m)
(hfail : (L - lam l a s) * nextB b s ≤ (M - bet b a s) * nextL l s)
(a' : Fin m → ℕ) (hpre : ∀ i : Fin m, i.val + 1 < s → a' i = a i)
(hlast : ∀ i : Fin m, i.val + 1 = s → a' i ≤ a i) (hfit : Fits l L a') :
bet b a' m ≤ M := by sorry
end CuttingStock63.Knapsack
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.