App. A.1, (7a)–(7d), p. 14 — Fourier–Motzkin elimination of (5) yields the system (7)
ProvedReluMIP.Ideal.fm_projection_eq_system7fourier-motzkinmixed-integer-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1projectionrelu
Let and with for every . Write for the sign-adjusted bounds (, if , swapped otherwise). The projection onto of the LP relaxation of the multiple choice formulation (5) equals the set of satisfying
This is the outcome of eliminating the auxiliary variables of (5) by Fourier–Motzkin elimination.
Formalization Note The page writes (7b) and (7c) with after replacing every negative weight by its absolute value through , so its display is the case ; undoing the substitution, as the last paragraph of A.1 does, turns into . The Lean states this general-sign form; (7b) is then literally (6b). 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, (7a)–(7d), p. 14 (arXiv:1811.08359v2): eliminating `x⁰, x¹, y⁰, y¹` from the LP
relaxation of (5) by Fourier–Motzkin yields the system (7), written here in general-sign form
(`L̆`, `Ŭ` in place of the page's `L`, `U` for `w > 0`). -/
theorem fm_projection_eq_system7 {η : ℕ} (w : Fin η → ℝ) (b : ℝ) (L U : Fin η → ℝ)
(hLU : ∀ i, L i < U i) :
relax5 w b L U = system7 w b L U := by sorry
end ReluMIP.Ideal
Source
arXiv:1811.08359v2, App. A.1, display (7a)–(7d), p. 14
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.