Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Customer Tolerances, p. 882 — for ζ = z₁/z₂, a basic feasible solution with no improving edge is a global minimum

Proved
CuttingStock63.Fractional.fractional_edge_criterion

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

cutting-stocklinear-fractional-programmingoptimality-criterionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1simplex-method

Let AAA be a real m×nm\times nm×n matrix, b∈Rmb\in\mathbb R^mb∈Rm, and c,d∈Rnc,d\in\mathbb R^nc,d∈Rn. Consider the linear-fractional program

minimizeζ(x)=z1(x)z2(x)=∑icixi∑idixisubject toAx=b, x≥0,\text{minimize}\quad \zeta(x)=\frac{z_1(x)}{z_2(x)}=\frac{\sum_i c_ix_i}{\sum_i d_ix_i}\qquad\text{subject to}\quad Ax=b,\ x\ge0,minimizeζ(x)=z2​(x)z1​(x)​=∑i​di​xi​∑i​ci​xi​​subject toAx=b, x≥0,

and assume the denominator is positive on the whole feasible set: ∑idixi>0\sum_i d_ix_i>0∑i​di​xi​>0 whenever Ax=bAx=bAx=b, x≥0x\ge0x≥0.

Let xˉ\bar xxˉ be a basic feasible solution with basis BBB (that is, ∣B∣=m|B|=m∣B∣=m, the columns ABA_BAB​ are linearly independent, and xˉk=0\bar x_k=0xˉk​=0 for k∉Bk\notin Bk∈/B). Suppose that no edge leading from xˉ\bar xxˉ improves the objective: for every nonbasic index j∉Bj\notin Bj∈/B and every edge direction vvv of xjx_jxj​ (so Av=0Av=0Av=0, vj=1v_j=1vj​=1, vk=0v_k=0vk​=0 for the other nonbasic kkk),

ddτ ζ(xˉ+τv)∣τ=0 ≥ 0.\frac{d}{d\tau}\,\zeta(\bar x+\tau v)\Big|_{\tau=0}\ \ge\ 0 .dτd​ζ(xˉ+τv)​τ=0​ ≥ 0.

Then xˉ\bar xxˉ is a global minimum:

ζ(xˉ)≤ζ(x)for every x with Ax=b, x≥0.\zeta(\bar x)\le\zeta(x)\qquad\text{for every } x \text{ with } Ax=b,\ x\ge0 .ζ(xˉ)≤ζ(x)for every x with Ax=b, x≥0.

This is the justification of the paper's claim that "the ordinary simplex method can be used" for a ratio objective: the method moves from vertex to vertex, testing only the edges at the current vertex, and stops when no edge improves. In the cutting stock problem with customer tolerances, ccc is the vector of pattern wastes wjw_jwj​, ddd is 111 on the pattern columns and 000 on the slack columns, so ζ\zetaζ is the fraction of waste.

Formalization Note The paper's sentence speaks of maximization; the statement is for minimization, the paper's actual problem ("minimize ζ\zetaζ", p. 881); the maximization version is the same statement applied to −c-c−c. "In a domain where the denominator does not vanish" is taken as positivity on the feasible set (the paper's footnote: ∑jxj>0\sum_jx_j>0∑j​xj​>0); on the convex feasible set a nonvanishing denominator has constant sign, and the negative case is the statement for (−c,−d)(-c,-d)(−c,−d). The upper bounds si≤Ni′′−Ni′s_i\le N_i''-N_i'si​≤Ni′′​−Ni′​ on the slacks are dropped, as the paper drops them on p. 882. The test quantifies over every nonbasic variable and every edge direction, feasible or not, as the simplex test does at a degenerate vertex; the derivative is Mathlib's deriv, the actual rate of change of ζ\zetaζ.

Preamble
import Mathlib
import Definitions.Def_DermanSeqDecisions_LinProg_LinearFractional
import Definitions.Def_MatousekLP_BFS_EquationalForm
import Definitions.Def_CuttingStock63_Fractional_Edge
Formal statement
namespace CuttingStock63.Fractional
open DermanSeqDecisions.LinProg
theorem fractional_edge_criterion {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
    (c d : Fin n → ℝ) (B : Finset (Fin n)) (xbar : Fin n → ℝ)
    (hden : ∀ x, IsFeasible11 A b x → 0 < ∑ i, d i * x i)
    (hxbar : IsBasicFeasibleFor A b B xbar)
    (hedge : ∀ j, j ∉ B → ∀ v, IsEdgeDirection A B j v →
      0 ≤ deriv (fun τ : ℝ => fracObj c d (xbar + τ • v)) 0) :
    ∀ x, IsFeasible11 A b x → fracObj c d xbar ≤ fracObj c d x := by sorry
end CuttingStock63.Fractional
Source
Gilmore & Gomory, A linear programming approach to the cutting stock problem—Part II, Opns. Res. 11 (1963), p. 882, Customer Tolerances, paragraph "It follows that the ordinary simplex method can be used to maximize a rational function … If no line yields any improvement, the calculation is finished" and its footnote; model of p. 881
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