Extreme points of integer-data polyhedra are bounded by
ProvedLinearOptimization.lp_bfs_integer_bound(Lemma 8.2, p. 373) Let be an integer matrix and let be a vector in [with integer entries]. Let be the largest absolute value of the entries in and .
- (a) Every extreme point of the polyhedron satisfies
- (b) Every extreme point of the standard form polyhedron satisfies
import Mathlib.Analysis.Convex.Extreme
import Definitions.Def_Polyhedron
open Matrix
/-- **Bertsimas & Tsitsiklis, Lemma 8.2 (p. 373).** Integer-data bound on extreme points:
(a) each coordinate of an extreme point of `{x | Ax ≥ b}` lies in
`[−(nU)ⁿ, (nU)ⁿ]`; (b) each coordinate of an extreme point of
`{x | Ax = b, x ≥ 0}` lies in `[−(mU)ᵐ, (mU)ᵐ]`. -/
theorem LinearOptimization.lp_bfs_integer_bound {m n : ℕ}
(A : Matrix (Fin m) (Fin n) ℤ) (b : Fin m → ℤ) (U : ℤ)
(hA : ∀ i j, |A i j| ≤ U) (hb : ∀ i, |b i| ≤ U) :
(∀ x ∈ Set.extremePoints ℝ
(polyhedron (A.map ((↑) : ℤ → ℝ)) (fun i => (b i : ℝ))),
∀ j, -(((n : ℝ) * (U : ℝ)) ^ n) ≤ x j ∧
x j ≤ ((n : ℝ) * (U : ℝ)) ^ n) ∧
(∀ x ∈ Set.extremePoints ℝ
(stdPolyhedron (A.map ((↑) : ℤ → ℝ)) (fun i => (b i : ℝ))),
∀ j, -(((m : ℝ) * (U : ℝ)) ^ m) ≤ x j ∧
x j ≤ ((m : ℝ) * (U : ℝ)) ^ m) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Fix an integer matrix , integer vector , and an integer with for all entries and (if this forces ; no lower bound like is assumed). All data are then cast to . The conclusion is a conjunction over two polyhedra. (a) Every extreme point of — extreme in the Mathlib sense: and whenever lies in the open segment between two points of , both endpoints equal — satisfies, for every coordinate , and , where is the number of variables. (b) Every extreme point of the standard-form polyhedron satisfies, for every , , where is the number of rows. All inequalities are non-strict and the bounds are resp. as real numbers (for or these degenerate to or accordingly).
Confirmed by the mission captain (proposal self-audit).