Theorem 6 — a non-optimal integral solution has an improving integral solution within distance
ProvedCookSensitivity.ChvatalRank.improving_vector_smallinteger-programmingp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1test-set
Let be a nonzero integral matrix, , , and consider the integer program . Then for each integral solution of , either is an optimal solution of the integer program, or there is an integral solution of with
Thus the integral vectors with entries at most in absolute value form a test set for every integer program with constraint matrix (improving on Graver and on Blair–Jeroslow); this is the ingredient that bounds the coefficients in Theorem 7.
Formalization Note No assumption that the integer program has an optimum is made: is arbitrary. The hypothesis is added: for , and , no is optimal and no at distance improves on .
Preamble
import Mathlib import Definitions.Def_CookSensitivity_ChvatalRank_maxSubdet import Definitions.Def_CookSensitivity_ChvatalRank_IntegerProgram
Formal statement
namespace CookSensitivity.ChvatalRank
open Matrix
theorem improving_vector_small {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℤ) (hA : A ≠ 0)
(b : Fin m → ℚ) (w : Fin n → ℚ)
(z : Fin n → ℚ) (hz : IsIntegral z) (hzP : z ∈ polyhedron A b) :
IsIPOptimal A b w z ∨
∃ zbar, IsIntegral zbar ∧ zbar ∈ polyhedron A b ∧
supNorm (z - zbar) ≤ (n : ℚ) * (maxSubdet A : ℚ) ∧ w ⬝ᵥ zbar > w ⬝ᵥ z := by sorry
end CookSensitivity.ChvatalRank
Source
Cook, Gerards, Schrijver, Tardos, Sensitivity theorems in integer linear programming, Math. Programming 34 (1986), p. 256, Theorem 6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.