Identical Prices, p. 869, paragraph ‘Clearly, identical prices …’ — among lengths with identical prices only the shortest is needed
ProvedCuttingStock63.Knapsack.identical_pricescutting-stockidentical-pricesknapsackp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be lengths and prices, and let be two items with and . Then for every vector of nonnegative integers with there is a vector with
(Substitute the shorter length for every piece of length .) Hence the maximum of the knapsack problem (1) is unchanged when the variable is dropped, and among lengths with identical prices only the shortest needs to be considered.
Formalization Note The page's remark that "the density associated with is greater" holds only for ; it is an aside and not part of the claim, which needs neither positive lengths nor the density order.
Preamble
import Mathlib import Definitions.Def_CuttingStock63_Knapsack_Problem
Formal statement
namespace CuttingStock63.Knapsack
/-- Identical Prices, paragraph "Clearly, identical prices …", p. 869: if l_i < l_j and b_i = b_j, then every vector
satisfying the constraint of (1) can be replaced by one with a_j = 0, still satisfying the
constraint, with the same objective (substitute l_i for every piece of length l_j). So the
maximum of (1) does not change when the variable a_j is dropped. -/
theorem identical_prices {m : ℕ} (l b : Fin m → ℝ) (L : ℝ) (i j : Fin m) (hij : i ≠ j)
(hlt : l i < l j) (hbeq : b i = b j) (a : Fin m → ℕ) (ha : Fits l L a) :
∃ a' : Fin m → ℕ, Fits l L a' ∧ a' j = 0 ∧ bet b a' m = bet b a 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. 869, Identical Prices, paragraph beginning ‘Clearly, identical prices’
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.