Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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)

Proved
CuttingStock63.Knapsack.knapsack_method_correct

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithm-correctnessbranch-and-boundknapsackp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1termination

Consider the Knapsack Method of Gilmore and Gomory (Steps (2)–(7)) with m≥1m\ge1m≥1 demanded lengths l1,…,lm>0l_1,\dots,l_m>0l1​,…,lm​>0, prices b1,…,bm≥0b_1,\dots,b_m\ge0b1​,…,bm​≥0, and k≥1k\ge1k≥1 stock lengths L1,…,LkL_1,\dots,L_kL1​,…,Lk​ with costs c1,…,ckc_1,\dots,c_kc1​,…,ck​, where the data are sorted as in Step (1):

b1l1≥b2l2≥⋯≥bmlm,L1>L2>⋯>Lk.\frac{b_1}{l_1}\ge\frac{b_2}{l_2}\ge\dots\ge\frac{b_m}{l_m},\qquad L_1>L_2>\dots>L_k .l1​b1​​≥l2​b2​​≥⋯≥lm​bm​​,L1​>L2​>⋯>Lk​.

Then:

  1. Termination. Every run from the start of Step (2) is finite: no reachable state begins an infinite sequence of steps.
  2. Progress. Every reachable state at which the method has not stopped has a next step.
  3. Correctness. At every reachable state at which the method has stopped, for every jjj, cj≤Mjc_j\le M_jcj​≤Mj​ and MjM_jMj​ is either cjc_jcj​ or the price ∑ibiai\sum_i b_ia_i∑i​bi​ai​ of a column with ∑iliai≤Lj\sum_i l_ia_i\le L_j∑i​li​ai​≤Lj​; and for the longest stock length
M1=max⁡(c1, max⁡{∑i=1mbiai:ai∈Z≥0, ∑i=1mliai≤L1}).M_1=\max\Big(c_1,\ \max\Big\{\sum_{i=1}^m b_ia_i : a_i\in\mathbb Z_{\ge0},\ \sum_{i=1}^m l_ia_i\le L_1\Big\}\Big).M1​=max(c1​, max{i=1∑m​bi​ai​:ai​∈Z≥0​, i=1∑m​li​ai​≤L1​}).

With a single stock length (k=1k=1k=1) this is the paper's claim, "the final values of the maxima MjM_jMj​ 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 Mj=max⁡(cj,Mˉj)M_j=\max(c_j,\bar M_j)Mj​=max(cj​,Mˉj​) for every jjj. That is false as the steps are printed when k≥2k\ge2k≥2: with m=1m=1m=1, l1=b1=1l_1=b_1=1l1​=b1​=1, L=(5,2)L=(5,2)L=(5,2), c=(0,0)c=(0,0)c=(0,0), the method tests (5)(5)(5) (so M1=5M_1=5M1​=5), the test of Step (5) at (4)(4)(4) holds for no jjj (j=1j=1j=1 fails the inequality, j=2j=2j=2 fails L2≥4L_2\ge4L2​≥4), Step (6) stops, and the run ends with M2=0M_2=0M2​=0 although the column (2)(2)(2) 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: li>0l_i>0li​>0 (demanded lengths) and bi≥0b_i\ge0bi​≥0; with a negative price the method is wrong (for m=2m=2m=2, b=(−1,−2)b=(-1,-2)b=(−1,−2), l=(1,1)l=(1,1)l=(1,1), L=2L=2L=2, c=−5c=-5c=−5 it ends with M=−2M=-2M=−2 although the zero vector gives 000), 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).

Preamble
import Mathlib
import Definitions.Def_CuttingStock63_Knapsack_Problem
import Definitions.Def_CuttingStock63_Knapsack_Method
Formal statement
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
Source
Gilmore & Gomory, A linear programming approach to the cutting stock problem—Part II, Opns. Res. 11 (1963), pp. 866–868, definition of M_j and Knapsack Method, Steps (1)–(7) and the paragraph after Step (7)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me