App. A.2, p. 15 — for small ε > 0 the η + 2 points p⁰, p¹, p̃ⁱ are feasible for (6) and tight on (6b)
ProvedReluMIP.Facet.facet_points_feasible_tightfacetmixed-integer-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1relu
Let , and with for every , and assume strict activity, for . Fix .
Then there is such that each of the points
is feasible with respect to formulation (6) — it satisfies (6a), every inequality (6b), , and — and satisfies the inequality (6b) for the subset at equality. Here if and if , and is the -th unit vector.
This is the first half of the proof of Proposition 2: it supplies points on the face of (6b).
Formalization Note The page assumes without loss of generality, so that , and every step is from or from ; the statement is the general-sign version, with the sign by which the step points into the box. Indices are 0-based (Fin η).
Preamble
import Mathlib import Definitions.Def_ReluMIP_Facet_Setting
Formal statement
namespace ReluMIP.Facet
/-- App. A.2, p. 15 (arXiv:1811.08359v2): for every `I ⊆ ReluMIP.Ideal.supp(w)` there is a step `ε > 0` such that
each of the `η + 2` points `p⁰, p¹, p̃ⁱ` of `facetPts` is feasible with respect to formulation (6)
and satisfies the inequality (6b) for `I` at equality. -/
theorem facet_points_feasible_tight {η : ℕ} (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 → ∃ ε : ℝ, 0 < ε ∧ ∀ j,
facetPts w b L U I ε j ∈ form6 w b L U ∧
(facetPts w b L U I ε j).2.1 =
ReluMIP.Ideal.rhs6b w b L U I (facetPts w b L U I ε j).1 (facetPts w b L U I ε j).2.2 := by sorry
end ReluMIP.Facet
Source
arXiv:1811.08359v2, App. A.2 (Proof of Proposition 2), second paragraph, p. 15
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.