Corollary 2 — the LP–IP optimal value gap is at most
ProvedCookSensitivity.ChvatalRank.lp_ip_value_gapinteger-programmingintegrality-gapp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximity
Let be an integral matrix, and such that has an integral solution and exists, attained at . Then is attained at some , and
This sharpens results of Blair and Jeroslow on the integrality gap and is the estimate (16) used in the proof of the Chvátal rank bound.
Formalization Note Existence of the integer optimum is part of the conclusion. No hypothesis is needed: for the LP maximum exists only if .
Preamble
import Mathlib import Definitions.Def_CookSensitivity_ChvatalRank_maxSubdet import Definitions.Def_CookSensitivity_ChvatalRank_IntegerProgram
Formal statement
namespace CookSensitivity.ChvatalRank
open Matrix
theorem lp_ip_value_gap {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℤ)
(b : Fin m → ℚ) (w : Fin n → ℚ)
(hint : ∃ x ∈ polyhedron A b, IsIntegral x)
(xbar : Fin n → ℚ) (hxbar : IsLPOptimal A b w xbar) :
∃ zbar, IsIPOptimal A b w zbar ∧
w ⬝ᵥ xbar - w ⬝ᵥ zbar ≤ (n : ℚ) * (maxSubdet A : ℚ) * l1Norm w := by sorry
end CookSensitivity.ChvatalRank
Source
Cook, Gerards, Schrijver, Tardos, Sensitivity theorems in integer linear programming, Math. Programming 34 (1986), p. 253, Corollary 2, eq. (4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.