§2.2, (5), pp. 5–6 — the multiple choice formulation is an ideal extended formulation of the ReLU graph
ProvedReluMIP.Ideal.multiple_choice_idealconvex-hullextended-formulationideal-formulationmixed-integer-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1relu
Let with , , and let with for every . Let be the lifted LP relaxation of (5) in , and its projection onto : the points with for which there are with
Then:
- Every extreme point of has , so (5) is ideal in its lifted space;
- with is a formulation of : lies on the graph if and only if for some ;
- is the convex hull of its points with :
The paper cites this fact from the literature on piecewise linear functions and from Balas's disjunctive programming; it is the starting point of the proof of Proposition 1.
Formalization Note The projected hull identity is the consequence of lifted ideality used in Appendix A.1. Strict activity is not assumed; the statement also holds without it.
Preamble
import Mathlib import Definitions.Def_ReluMIP_Ideal_Setting import Definitions.Def_ReluMIP_Ideal_Lifted5
Formal statement
namespace ReluMIP.Ideal
/-- §2.2, display (5), pp. 5–6 (arXiv:1811.08359v2): the multiple-choice formulation (5) is an
ideal extended formulation of `gr(ReLU ∘ f; [L, U])`. Its lifted LP relaxation has binary
extreme points in `z`; with `z ∈ {0,1}` it formulates the graph; and its projection to
`(x,y,z)` is the convex hull of its points with `z ∈ {0,1}`. -/
theorem multiple_choice_ideal {η : ℕ} (w : Fin η → ℝ) (b : ℝ) (L U : Fin η → ℝ)
(hLU : ∀ i, L i < U i) :
(∀ p ∈ Set.extremePoints ℝ (relax5Lift w b L U), p.1.2.2 = 0 ∨ p.1.2.2 = 1) ∧
IsFormulationFor (relax5 w b L U) (reluGraph w b L U) ∧
relax5 w b L U = convexHull ℝ {p | p ∈ relax5 w b L U ∧ (p.2.2 = 0 ∨ p.2.2 = 1)} := by sorry
end ReluMIP.Ideal
Source
arXiv:1811.08359v2, §2.2, display (5a)–(5f), pp. 5–6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.