Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Knapsack Method, p. 868 — after a failed test in Step (5), no vector before the successor of Step (6) improves M_j

Proved
CuttingStock63.Knapsack.successor_bound

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

boundbranch-and-boundknapsackp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let l1,…,lm>0l_1,\dots,l_m>0l1​,…,lm​>0 and b1,…,bm≥0b_1,\dots,b_m\ge0b1​,…,bm​≥0 be ordered by density, b1/l1≥⋯≥bm/lmb_1/l_1\ge\dots\ge b_m/l_mb1​/l1​≥⋯≥bm​/lm​, with the slack item bm+1=0b_{m+1}=0bm+1​=0, lm+1=1l_{m+1}=1lm+1​=1. Let 1≤s≤m1\le s\le m1≤s≤m, let (α)s(\alpha)_s(α)s​ be a prefix, and let LLL, MMM be a stock length and its current maximum such that the inequality of the test of Step (5) fails:

(L−λ⋅(α)s) bs+1  ≤  (M−β⋅(α)s) ls+1.(L-\lambda\cdot(\alpha)_s)\,b_{s+1}\;\le\;(M-\beta\cdot(\alpha)_s)\,l_{s+1}.(L−λ⋅(α)s​)bs+1​≤(M−β⋅(α)s​)ls+1​.

Then every vector (α′)m(\alpha')_m(α′)m​ of nonnegative integers with ai′=aia'_i=a_iai′​=ai​ for i≤s−1i\le s-1i≤s−1, as′≤asa'_s\le a_sas′​≤as​ and L≥λ⋅(α′)mL\ge\lambda\cdot(\alpha')_mL≥λ⋅(α′)m​ satisfies β⋅(α′)m≤M\beta\cdot(\alpha')_m\le Mβ⋅(α′)m​≤M.

These are exactly the vectors lexicographically between (α)s(\alpha)_s(α)s​ and the successor computed in Step (6), the lexicographically largest (s−1)(s-1)(s−1)-vector smaller than (α)s(\alpha)_s(α)s​; so after a failed test the method may jump to that successor without missing an improvement of MMM.

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 jjj; but the test of Step (5) for jjj also requires Lj≥λ⋅(α)sL_j\ge\lambda\cdot(\alpha)_sLj​≥λ⋅(α)s​, and when that part fails for a shorter stock length, smaller values of asa_sas​ may still fit LjL_jLj​ and improve MjM_jMj​. The statement therefore assumes the failure of the inequality itself (which is what the test establishes for every jjj whose length accommodates the prefix). Nonnegative prices are a disclosed hypothesis, as for the relaxation bound.

Preamble
import Mathlib
import Definitions.Def_CuttingStock63_Knapsack_Problem
Formal statement
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
Source
Gilmore & Gomory, A linear programming approach to the cutting stock problem—Part II, Opns. Res. 11 (1963), p. 868, Knapsack Method, paragraph before Step (5) (successor calculated in (6))
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