Display (10), p. 464 — the optimal x* of THEOREM 4 satisfies ∏(1 + x_{m+i}) ≤ D
ProvedGomory69.Asymptotic.display_10asymptotic-integer-programminggroup-polyhedroninteger-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Under the hypotheses of THEOREM 4 (, an optimal LP basis, a vertex of minimizing (8), a corresponding vertex using only least cost columns), the optimal integer solution of (2) also satisfies
So there are optimal integer programming solutions whose nonbasic part is small in this multiplicative sense.
Formalization Note The paper says "there are optimal integer programming solutions to (2) with" this bound; it is stated here for the specific optimal solution built from a minimizing vertex, which is the solution the paper's argument produces (the existence of a minimizing vertex is taken for granted on p. 461 and is not part of this statement).
Preamble
import Mathlib import Definitions.Def_Gomory69_Asymptotic_GroupPolyhedron import Definitions.Def_Gomory69_Asymptotic_IntegerProgram
Formal statement
namespace Gomory69.Asymptotic
/-- Display (10) (p. 464): under the hypotheses of THEOREM 4, the optimal solution
`x* = (B⁻¹(b − N x_N*), x_N*)` obtained from a minimizing vertex also satisfies
`∏_{i=1}^{n} (1 + x*_{m+i}) ≤ D`, `D = |det B|`. -/
theorem display_10 {m n : ℕ} (B : Matrix (Fin m) (Fin m) ℤ) (N : Matrix (Fin m) (Fin n) ℤ)
(b : Fin m → ℤ) (c : Fin m ⊕ Fin n → ℝ)
(hunit : ContainsUnitMatrix B N) (hdet : B.det ≠ 0) (hopt : IsOptimalLPBasis B N b c)
(hb : realVec b ∈ deepCone B (lmax N * ((detAbs B : ℝ) - 1)))
(tstar : ↥(groupColumnSet B N) → ℝ) (ht : IsMinimizingVertex B N b c tstar)
(xN : Fin n → ℕ) (hx : IsCorrespondingVertex B N c tstar xN) :
∃ xB : Fin m → ℤ, (∀ k, (xB k : ℝ) = basicPart B N b xN k) ∧
IsOptimal B N b c (Sum.elim xB (fun i => (xN i : ℤ))) ∧
∏ i : Fin n, (1 + xN i) ≤ detAbs B := by sorry
end Gomory69.Asymptotic
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), p. 464, display (10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.