Proposition 2, p. 6 — under strict activity each inequality in (6b) is facet-defining
ProvedReluMIP.Facet.proposition_2Let with , , over the input box with for every , and assume strict activity, . Let be the convex hull of the points feasible with respect to formulation (6):
Then for every the inequality (6b) for ,
is facet-defining for : it is valid on , the face of on which it holds with equality is nonempty, and .
Together with Proposition 1 (formulation (6) is ideal), this says that none of the exponentially many inequalities (6b) can be dropped: formulation (6) is minimal modulo variable bounds. The paper notes that strict activity is required for this result.
Formalization Note "Facet-defining" is not defined in the paper; the standard notion is used, with dimensions as finrank of the vectorSpan and written . The polyhedron is the convex hull of the points of (6) (with ), which by Proposition 1 equals the LP relaxation of (6); the hull is used so that the statement does not depend on Proposition 1. The bounds and strict activity are the paper's standing assumptions of §1.3. Indices are 0-based (Fin η).
import Mathlib import Definitions.Def_ReluMIP_Facet_Setting
namespace ReluMIP.Facet
/-- Proposition 2, p. 6 (arXiv:1811.08359v2): under the standing assumptions of §1.3
(`L < U` componentwise and strict activity `M⁻(f) < 0 < M⁺(f)`), each inequality (6b),
`y ≤ ∑_{i∈I} wᵢ(xᵢ − L̆ᵢ(1 − z)) + (b + ∑_{i∉I} wᵢŬᵢ) z` for `I ⊆ ReluMIP.Ideal.supp(w)`, is facet-defining for
the convex hull of the points feasible with respect to formulation (6). -/
theorem proposition_2 {η : ℕ} (w : Fin η → ℝ) (b : ℝ) (L U : Fin η → ℝ)
(hLU : ∀ i, L i < U i) (hSA : ReluMIP.Ideal.StrictActivity w b L U) :
∀ I : Finset (Fin η), I ⊆ ReluMIP.Ideal.supp w →
IsFacetDefining (convexHull ℝ (form6 w b L U))
(fun p => p.2.1 - ReluMIP.Ideal.rhs6b w b L U I p.1 p.2.2) := by sorry
end ReluMIP.Facet
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.