App. A.1, pp. 14–15 — the family (7c) is redundant given (7a), (7b), (7d)
ProvedReluMIP.Ideal.system7c_redundantmixed-integer-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1redundant-inequalityrelu
Let and , with sign-adjusted bounds . Every point of the LP relaxation of formulation (6), that is, every point satisfying (7a), (7b) and (7d), also satisfies every inequality of the family (7c):
Together with the Fourier–Motzkin step, this shows that the projection of the multiple choice formulation (5) is exactly the LP relaxation of (6).
Formalization Note No hypothesis on or strict activity is needed, so none is assumed. The inequality (7c) is stated in the general-sign form explained in the Fourier–Motzkin milestone.
Preamble
import Mathlib import Definitions.Def_ReluMIP_Ideal_Setting
Formal statement
namespace ReluMIP.Ideal
/-- App. A.1, pp. 14–15 (arXiv:1811.08359v2): the family (7c) is redundant — every point of the
LP relaxation of (6) (that is, of (7a), (7b), (7d)) satisfies every inequality of (7c). -/
theorem system7c_redundant {η : ℕ} (w : Fin η → ℝ) (b : ℝ) (L U : Fin η → ℝ) :
∀ p ∈ relax6 w b L U, ∀ I : Finset (Fin η), I ⊆ supp w →
rhs7c w b L U I p.1 p.2.2 ≤ p.2.1 := by sorry
end ReluMIP.Ideal
Source
arXiv:1811.08359v2, App. A.1, pp. 14–15 (the paragraph after display (7))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.