THEOREM 4, p. 462 — for b ∈ K_B(l_max(D − 1)) a minimizing vertex gives an optimal integer solution
ProvedGomory69.Asymptotic.theorem_4Consider the integer program (2), subject to , integer, with an integer matrix containing an unit matrix, nonsingular and an optimal basis of the linear programming relaxation (all relative prices , ). Let , the Euclidean length of the longest nonbasic column, , the set of nonzero , and suppose
Let be a vertex of minimizing (8), over the nonnegative integer solutions of , and let be the nonbasic part of a corresponding vertex of using only least cost columns. Then is a nonnegative integer vector and is an optimal integer solution of (2).
This is the asymptotic theorem of integer programming in its vertex form: for right-hand sides far enough inside the cone of an optimal LP basis, the integer program is solved by the group problem, and the answer can be read off a vertex of the corner polyhedron.
Formalization Note "The of Theorem 3" is spelled out: is an extreme point of that minimizes (8) over the integer solutions, and satisfies Remark 1 (i)–(iii) and the least-cost condition. uses Euclidean distance to the frontier of . The conclusion states that the basic part is integral, nonnegativity and feasibility being part of optimality.
import Mathlib import Definitions.Def_Gomory69_Asymptotic_GroupPolyhedron import Definitions.Def_Gomory69_Asymptotic_IntegerProgram
namespace Gomory69.Asymptotic
/-- THEOREM 4 (p. 462): let `B` be an optimal linear programming basis of (2), `D = |det B|`,
`l_max` the Euclidean length of the longest nonbasic column, and `b ∈ K_B(l_max (D − 1))`.
If `t*` is a vertex of `P(𝒢, 𝒩, f b)` minimizing (8) and `x_N*` the nonbasic part of a
corresponding vertex using only least cost columns, then `x_B* = B⁻¹(b − N x_N*)` is an
integer vector and `x* = (x_B*, x_N*)` is an optimal solution of the integer program (2). -/
theorem theorem_4 {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 : ℤ))) := by sorry
end Gomory69.Asymptotic
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.