Theorem 1 — LP and IP optima lie within -distance of each other
ProvedCookSensitivity.ChvatalRank.lp_ip_proximityinteger-programmingp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximitysensitivity
Let be a nonzero integral matrix, , , and let be the largest absolute value of a subdeterminant of . Suppose has an integral solution and exists. Then
- for each optimal solution of there is an optimal solution of with
- for each optimal solution of there is an optimal solution of with .
In particular the integer program has an optimal solution. The bound depends only on the number of variables and on , not on or ; it is the basis of every other proximity and sensitivity result of the paper.
Formalization Note The hypothesis is added. For one has , and with , and a non-integral part 1 would ask for an integral point at distance , which is false; the paper's proof assumes it implicitly (cf. "we may assume ", p. 257).
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_proximity {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℤ) (hA : A ≠ 0)
(b : Fin m → ℚ) (w : Fin n → ℚ)
(hint : ∃ x ∈ polyhedron A b, IsIntegral x)
(hmax : ∃ x, IsLPOptimal A b w x) :
(∀ xbar, IsLPOptimal A b w xbar →
∃ zstar, IsIPOptimal A b w zstar ∧
supNorm (xbar - zstar) ≤ (n : ℚ) * (maxSubdet A : ℚ)) ∧
(∀ zbar, IsIPOptimal A b w zbar →
∃ xstar, IsLPOptimal A b w xstar ∧
supNorm (zbar - xstar) ≤ (n : ℚ) * (maxSubdet A : ℚ)) := by sorry
end CookSensitivity.ChvatalRank
Source
Cook, Gerards, Schrijver, Tardos, Sensitivity theorems in integer linear programming, Math. Programming 34 (1986), p. 252, Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.