Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Customer Tolerances, p. 882 — a ratio of linear functions is uniformly increasing or decreasing along a line avoiding the zeros of its denominator

Proved
CuttingStock63.Fractional.ratio_monotone_on_line

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

derivativelinear-fractional-programmingmonotonicityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let c,d,x,v∈Rnc,d,x,v\in\mathbb R^nc,d,x,v∈Rn and consider the ratio of two linear functions restricted to the line through xxx in direction vvv,

f(τ)=ζ(x+τv)=∑ici(xi+τvi)∑idi(xi+τvi),D(τ)=∑idi(xi+τvi).f(\tau)=\zeta(x+\tau v)=\frac{\sum_i c_i(x_i+\tau v_i)}{\sum_i d_i(x_i+\tau v_i)},\qquad D(\tau)=\sum_i d_i(x_i+\tau v_i).f(τ)=ζ(x+τv)=∑i​di​(xi​+τvi​)∑i​ci​(xi​+τvi​)​,D(τ)=i∑​di​(xi​+τvi​).

Let I⊆RI\subseteq\mathbb RI⊆R be an interval on which the denominator DDD does not vanish. Then:

  1. fff is strictly increasing on III, or strictly decreasing on III, or constant on III;
  2. the derivative changes along III only by a positive factor: for all τ,τ′∈I\tau,\tau'\in Iτ,τ′∈I,
f′(τ) D(τ)2=f′(τ′) D(τ′)2.f'(\tau)\,D(\tau)^2=f'(\tau')\,D(\tau')^2 .f′(τ)D(τ)2=f′(τ′)D(τ′)2.

In particular f′f'f′ has the same sign at every point of III.

This is what lets the simplex method be used for a ratio objective: along an edge the objective cannot first improve and then deteriorate, so the local test at a vertex decides the whole edge.

Formalization Note The page says the derivative "will have the same value vvv" at every point of the line; this is false when the denominator is not constant along the line (the derivative of (α+βτ)/(γ+δτ)(\alpha+\beta\tau)/(\gamma+\delta\tau)(α+βτ)/(γ+δτ) is (βγ−αδ)/(γ+δτ)2(\beta\gamma-\alpha\delta)/(\gamma+\delta\tau)^2(βγ−αδ)/(γ+δτ)2). The statement formalizes the correct version, which is what "uniformly increasing or decreasing" and the simplex argument need: the derivative times the squared denominator is constant. The page's "rational function" is the ratio z1/z2z_1/z_2z1​/z2​ of two linear functions of p. 881, Derman's published fracObj. The page speaks of a whole line; the statement is for any interval III (the whole line being I=RI=\mathbb RI=R), which is the stronger form used along a segment of the feasible set.

Preamble
import Mathlib
import Definitions.Def_DermanSeqDecisions_LinProg_LinearFractional
Formal statement
namespace CuttingStock63.Fractional
open DermanSeqDecisions.LinProg
theorem ratio_monotone_on_line {n : ℕ} (c d x v : Fin n → ℝ) (I : Set ℝ)
    (hI : IsPreconnected I) (hden : ∀ τ ∈ I, ∑ i, d i * (x + τ • v) i ≠ 0) :
    (StrictMonoOn (fun τ : ℝ => fracObj c d (x + τ • v)) I ∨
      StrictAntiOn (fun τ : ℝ => fracObj c d (x + τ • v)) I ∨
      ∀ τ ∈ I, ∀ τ' ∈ I, fracObj c d (x + τ • v) = fracObj c d (x + τ' • v)) ∧
    ∀ τ ∈ I, ∀ τ' ∈ I,
      deriv (fun s : ℝ => fracObj c d (x + s • v)) τ * (∑ i, d i * (x + τ • v) i) ^ 2 =
        deriv (fun s : ℝ => fracObj c d (x + s • v)) τ' * (∑ i, d i * (x + τ' • v) i) ^ 2 := 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 is easy to show by direct differentiation …"
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