Theorem 5 — optimal solutions move by at most (LP) and (IP)
ProvedCookSensitivity.ChvatalRank.rhs_sensitivityinteger-programmingp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximitysensitivity
Let be an integral matrix and , such that and both have optimal solutions. Then
- for each optimal solution of there is an optimal solution of with
- if and both have integral solutions, then for each optimal solution of there is an optimal solution of with
A change of the right-hand side therefore moves optimal solutions, and hence optimal values, by an amount affine in , sharpening a result of Blair and Jeroslow.
Formalization Note No hypothesis is needed; for both parts hold with , .
Preamble
import Mathlib import Definitions.Def_CookSensitivity_ChvatalRank_maxSubdet import Definitions.Def_CookSensitivity_ChvatalRank_IntegerProgram
Formal statement
namespace CookSensitivity.ChvatalRank
open Matrix
theorem rhs_sensitivity {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℤ)
(b b' : Fin m → ℚ) (w : Fin n → ℚ)
(hmax : ∃ x, IsLPOptimal A b w x) (hmax' : ∃ x, IsLPOptimal A b' w x) :
(∀ xbar, IsLPOptimal A b w xbar →
∃ xbar', IsLPOptimal A b' w xbar' ∧
supNorm (xbar - xbar') ≤ (n : ℚ) * (maxSubdet A : ℚ) * supNorm (b - b')) ∧
((∃ x ∈ polyhedron A b, IsIntegral x) → (∃ x ∈ polyhedron A b', IsIntegral x) →
∀ zbar, IsIPOptimal A b w zbar →
∃ zbar', IsIPOptimal A b' w zbar' ∧
supNorm (zbar - zbar') ≤ (n : ℚ) * (maxSubdet A : ℚ) * (supNorm (b - b') + 2)) := by sorry
end CookSensitivity.ChvatalRank
Source
Cook, Gerards, Schrijver, Tardos, Sensitivity theorems in integer linear programming, Math. Programming 34 (1986), p. 255, Theorem 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.