Proposition 1, p. 6 — (6a)–(6c) is an ideal formulation of gr(ReLU∘f; [L, U])
ProvedReluMIP.Ideal.proposition_1ideal-formulationmixed-integer-programmingneural-networkp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1relu
Let be an affine function with and , over the input domain with for every , and assume strict activity: , where and are the maximum and minimum of on . Then
is an ideal formulation of . That is:
- if and only if satisfies (6a)–(6c) for some ;
- every extreme point of the LP relaxation of (6) (with in place of ) has .
The formulation uses only the original variables and one binary variable, with exponentially many inequalities (6b); it is the strongest possible tightening of the big-M formulation (3).
Formalization Note The two hypotheses and strict activity are the standing assumptions of §1.3 of the paper. "Ideal" follows the paper's definition (p. 3): the extreme points of the LP relaxation are integral; only is an integer variable, so integrality concerns alone.
Preamble
import Mathlib import Definitions.Def_ReluMIP_Ideal_Setting
Formal statement
namespace ReluMIP.Ideal
/-- Proposition 1, p. 6 (arXiv:1811.08359v2; proof App. A.1, pp. 14–15): for `f(x) = w · x + b`
over `[L, U]` (with the standing assumptions of §1.3: `Lᵢ < Uᵢ` and strict activity), (6a)–(6c) is
an ideal formulation of `gr(ReLU ∘ f; [L, U])`: together with `z ∈ {0, 1}` its LP relaxation
formulates the graph, and every extreme point of the LP relaxation has `z ∈ {0, 1}`. -/
theorem proposition_1 {η : ℕ} (w : Fin η → ℝ) (b : ℝ) (L U : Fin η → ℝ)
(hLU : ∀ i, L i < U i) (hSA : StrictActivity w b L U) :
IsFormulationFor (relax6 w b L U) (reluGraph w b L U) ∧ IsIdeal (relax6 w b L U) := by sorry
end ReluMIP.Ideal
Source
arXiv:1811.08359v2, Proposition 1, p. 6 (proof App. A.1, pp. 14–15); standing assumptions §1.3, p. 4; definition of ideal §1.1, p. 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.