Knapsack Method, pp. 867–868 — every run terminates, never gets stuck, and ends with M_1 = max(c_1, the knapsack optimum for L_1)
ProvedCuttingStock63.Knapsack.knapsack_method_correctConsider the Knapsack Method of Gilmore and Gomory (Steps (2)–(7)) with demanded lengths , prices , and stock lengths with costs , where the data are sorted as in Step (1):
Then:
- Termination. Every run from the start of Step (2) is finite: no reachable state begins an infinite sequence of steps.
- Progress. Every reachable state at which the method has not stopped has a next step.
- Correctness. At every reachable state at which the method has stopped, for every , and is either or the price of a column with ; and for the longest stock length
With a single stock length () this is the paper's claim, "the final values of the maxima are the desired maxima when the algorithm terminates in Step (6)", in full: the method solves the knapsack problem (1).
Formalization Note The page claims for every . That is false as the steps are printed when : with , , , , the method tests (so ), the test of Step (5) at holds for no ( fails the inequality, fails ), Step (6) stops, and the run ends with although the column has price 2. (A sorry-free Lean proof of this run accompanies the mission.) The statement keeps the printed algorithm and claims exactly what holds for it. Disclosed hypotheses: (demanded lengths) and ; with a negative price the method is wrong (for , , , , it ends with although the zero vector gives ), and the paper applies it to cutting-stock prices, which are nonnegative. Step (1) is stated as hypotheses on the input rather than as a sorting step. Termination is part of the statement so that the correctness clause is not vacuous; the algorithm's output is never defined as the knapsack maximum, and the maximum is the predicate IsKnapsackMax, not a real sSup (which is 0 on an empty set).
import Mathlib import Definitions.Def_CuttingStock63_Knapsack_Problem import Definitions.Def_CuttingStock63_Knapsack_Method
namespace CuttingStock63.Knapsack
/-- Knapsack Method, Steps (1)–(7) and the paragraph after Step (7), p. 868, in corrected form:
for data sorted as in Step (1), every run of the method from Step (2) is finite, a state other
than the end always has a next step, and at the end every M_j is c_j or attained by a vector
satisfying L_j ≥ λ·(α)_m with c_j ≤ M_j, while M_1 (the longest stock length) is exactly
max(c_1, M̄_1). With one stock length (k = 1) this is the paper's claim in full. -/
theorem knapsack_method_correct {m k : ℕ} (hm : 0 < m) (hk : 0 < k) (l b : Fin m → ℝ)
(L c : Fin k → ℝ) (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) (hL : StrictAnti L) :
(∀ σ : State m k, Reachable l b L c hk σ → Acc (fun x y => Step l b L c y x) σ) ∧
(∀ σ : State m k, Reachable l b L c hk σ → σ.phase ≠ .done →
∃ σ' : State m k, Step l b L c σ σ') ∧
(∀ σ : State m k, Reachable l b L c hk σ → σ.phase = .done →
(∀ j : Fin k, c j ≤ σ.M j ∧
(σ.M j = c j ∨ ∃ a : Fin m → ℕ, Fits l (L j) a ∧ bet b a m = σ.M j)) ∧
IsKnapsackMax l b (L ⟨0, hk⟩) (c ⟨0, hk⟩) (σ.M ⟨0, hk⟩)) := by sorry
end CuttingStock63.Knapsack
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.