App. A.1, p. 14 — the LP relaxation of (6) is the convex hull of its points with z ∈ {0, 1}
ProvedReluMIP.Ideal.relax6_eq_convexHullconvex-hullideal-formulationmixed-integer-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1relu
Let and with for every . Let be the LP relaxation of formulation (6): the points with and, for every ,
Then
This is the content of the first sentence of Appendix A.1: is the projection of the ideal extended formulation (5), so it inherits its integrality. Proposition 1 follows from it.
Formalization Note Strict activity is not assumed (the identity holds without it).
Preamble
import Mathlib import Definitions.Def_ReluMIP_Ideal_Setting
Formal statement
namespace ReluMIP.Ideal
/-- App. A.1, p. 14 (arXiv:1811.08359v2): the LP relaxation of (6) is the projection of the ideal
extended formulation (5), hence equals the convex hull of its points with `z ∈ {0, 1}`. -/
theorem relax6_eq_convexHull {η : ℕ} (w : Fin η → ℝ) (b : ℝ) (L U : Fin η → ℝ)
(hLU : ∀ i, L i < U i) :
relax6 w b L U = convexHull ℝ {p | p ∈ relax6 w b L U ∧ (p.2.2 = 0 ∨ p.2.2 = 1)} := by sorry
end ReluMIP.Ideal
Source
arXiv:1811.08359v2, App. A.1, first sentence, p. 14
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.