p. 854, step (3) — a nonbasic surplus variable prices out when its multiplier is negative
ProvedGilmoreGomory61.CuttingStock.step3_slack_testcutting-stockp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1simplex-methodsurplus-variable
Let a current feasible basis be fixed. A nonbasic surplus variable in demand row can participate with the basic columns in a strictly cheaper feasible solution only if the corresponding first-row entry of is negative:
If all basic values are strictly positive, the converse holds. This is the surplus-column test used before searching for a new cutting activity.
Formalization Note The paper's st bordered row is the demand row at Lean index . The converse needs nondegeneracy, as acknowledged by the paper's separate zero-ratio procedure.
Preamble
import Mathlib import Definitions.Def_GilmoreGomory61_CuttingStock_Basis
Formal statement
namespace GilmoreGomory61.CuttingStock
/-- Routine step (3): a nonbasic surplus variable prices out exactly for negative multiplier. -/
theorem step3_slack_test {m k : ℕ} (I : Instance m k)
(β : Fin m → Col I) (hβ : IsFeasibleBasis I β)
(i : Fin m) (hi : Sum.inr i ∉ Set.range β) :
(Improves I β (Sum.inr i) → mult I β i < 0) ∧
(IsNondegenerate I β → mult I β i < 0 → Improves I β (Sum.inr i)) := by sorry
end GilmoreGomory61.CuttingStock
Source
Gilmore and Gomory, A linear programming approach to the cutting-stock problem, Oper. Res. 9(6) (1961), p. 854, step (3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.