Extreme points of integer-data polyhedra are bounded by
ProvedLinearOptimization.lp_bfs_integer_boundcomplexityellipsoid-methodextreme-pointsinteger-data
(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
Preamble
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)ᵐ]`. -/
Formal statement
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
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Lemma 8.2, p. 373