Customer Tolerances, p. 882 — for ζ = z₁/z₂, a basic feasible solution with no improving edge is a global minimum
ProvedCuttingStock63.Fractional.fractional_edge_criterionLet be a real matrix, , and . Consider the linear-fractional program
and assume the denominator is positive on the whole feasible set: whenever , .
Let be a basic feasible solution with basis (that is, , the columns are linearly independent, and for ). Suppose that no edge leading from improves the objective: for every nonbasic index and every edge direction of (so , , for the other nonbasic ),
Then is a global minimum:
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, is the vector of pattern wastes , is on the pattern columns and on the slack columns, so 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 ", p. 881); the maximization version is the same statement applied to . "In a domain where the denominator does not vanish" is taken as positivity on the feasible set (the paper's footnote: ); on the convex feasible set a nonvanishing denominator has constant sign, and the negative case is the statement for . The upper bounds 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 .
import Mathlib import Definitions.Def_DermanSeqDecisions_LinProg_LinearFractional import Definitions.Def_MatousekLP_BFS_EquationalForm import Definitions.Def_CuttingStock63_Fractional_Edge
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.