Lemma 6.1, p. 21 — a rational MICP-R set splits into a binary MICP-R set and rational pieces whose I_ℤ has an integer point in its relative interior
ProvedMICPRep.Periodic.lemma_6_1mixed-integer-convex-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1rationally-unboundedrepresentability
Let be closed and convex such that induces a rational MICP formulation of a nonempty set . Then there are a binary MICP-R set , and closed convex sets such that each induces a rational MICP formulation of a nonempty set ,
and for each , with the index set of ,
This is the first of the two key lemmas behind Theorem 5.1: it reduces to formulations whose index sets are "integrally full-dimensional".
Formalization Note The sets live in the same as (same and ), as "" says; the relative interior is intrinsicInterior.
Preamble
import Mathlib import Definitions.Def_MICPRep_Periodic_Setting
Formal statement
namespace MICPRep.Periodic
open scoped ENNReal Matrix
/-- Lemma 6.1, p. 21. -/
theorem lemma_6_1 {n p d : ℕ} (M : Set (Ambient n p d)) (S : Set (Pt n))
(hM : IsRationalFormulation M S) (hS : S.Nonempty) :
∃ S₀ : Set (Pt n), IsBinaryMICPR S₀ ∧
∃ (k : ℕ) (Ms : Fin k → Set (Ambient n p d)) (Ss : Fin k → Set (Pt n)),
(∀ i, IsRationalFormulation (Ms i) (Ss i) ∧ (Ss i).Nonempty) ∧
S = S₀ ∪ ⋃ i, Ss i ∧
∀ i, micpDiam (Ms i) ≤ micpDiam M ∧
(intrinsicInterior ℝ (IZ (indexSet (Ms i))) ∩ intLattice d).Nonempty := by sorry
end MICPRep.Periodic
Source
Lubin, Vielma, Zadik, Mixed-integer convex representability, arXiv:1706.05135v3, p. 21, Lemma 6.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.