Customer Tolerances, p. 883 — column choice for the ratio objective is again a knapsack problem (with Π̄ᵢ = −(z₁Π²ᵢ − z₂Π¹ᵢ − z₂lᵢ))
ProvedCuttingStock63.Fractional.column_choice_knapsackFix a stock length , piece lengths , the current values of the two auxiliary objectives, and vectors (in the paper, the last entries of the first two rows and of the basis inverse). A cutting pattern is a vector ; its waste is (eq. (4)) and its column is . Consider the bracket of (5),
so that . Then:
- (third line of (5)) ;
- (after substituting (4)) with and ,
- if , a pattern with minimizes over all patterns that fit in if and only if it maximizes subject to , .
Hence choosing the column with the most negative is a knapsack problem with values , exactly as for the linear objective of Part I; only the values change.
Formalization Note The page prints the coefficient inside the sum after substituting (4), and . Substituting into gives , so the correct coefficient is ; the statement uses the corrected one (the two agree when ). The identities hold for arbitrary , in particular for the rows of any basis inverse.
import Mathlib
namespace CuttingStock63.Fractional
theorem column_choice_knapsack {m : ℕ} (L z₁ z₂ : ℝ) (l p₁ p₂ : Fin m → ℝ) :
(∀ a : Fin m → ℕ,
z₁ * (-1 + ∑ i, p₂ i * a i) - z₂ * (-(L - ∑ i, (a i : ℝ) * l i) + ∑ i, p₁ i * a i) =
(L - ∑ i, (a i : ℝ) * l i) * z₂ - z₁ + ∑ i, (z₁ * p₂ i - z₂ * p₁ i) * a i) ∧
(∀ a : Fin m → ℕ,
z₁ * (-1 + ∑ i, p₂ i * a i) - z₂ * (-(L - ∑ i, (a i : ℝ) * l i) + ∑ i, p₁ i * a i) =
(L * z₂ - z₁) - ∑ i, (-(z₁ * p₂ i - z₂ * p₁ i - z₂ * l i)) * a i) ∧
(z₂ ≠ 0 → ∀ a : Fin m → ℕ, ∑ i, (a i : ℝ) * l i ≤ L →
((∀ a' : Fin m → ℕ, ∑ i, (a' i : ℝ) * l i ≤ L →
(z₁ * (-1 + ∑ i, p₂ i * a i) - z₂ * (-(L - ∑ i, (a i : ℝ) * l i) + ∑ i, p₁ i * a i)) /
z₂ ^ 2 ≤
(z₁ * (-1 + ∑ i, p₂ i * a' i) -
z₂ * (-(L - ∑ i, (a' i : ℝ) * l i) + ∑ i, p₁ i * a' i)) / z₂ ^ 2) ↔
(∀ a' : Fin m → ℕ, ∑ i, (a' i : ℝ) * l i ≤ L →
∑ i, (-(z₁ * p₂ i - z₂ * p₁ i - z₂ * l i)) * a' i ≤
∑ i, (-(z₁ * p₂ i - z₂ * p₁ i - z₂ * l i)) * a i))) := by sorry
end CuttingStock63.Fractional
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.