Lemma 6.2, p. 22 — trichotomy: binary MICP-R, or a nearly periodic formulation, or a rational formulation with d − 1 integer variables sandwiched between S and cl(S)
ProvedMICPRep.Periodic.lemma_6_2mixed-integer-convex-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1periodic-setrepresentability
Let be closed and convex such that induces a rational MICP formulation of a nonempty set with index set . If and has an integer point in its relative interior, then one of the following holds:
- is binary MICP-R;
- has a nearly periodic MICP formulation;
- there is a closed convex such that induces a rational MICP formulation of a nonempty set with
This is the second key lemma behind Theorem 5.1; option 3 feeds the induction on the number of integer variables.
Formalization Note "" is written via , so option 3 is impossible when (no truncated subtraction). The number of continuous variables of is existential. The nearly periodic formulation in option 2 may be any MICP formulation of , not necessarily rational.
Preamble
import Mathlib import Definitions.Def_MICPRep_Periodic_Setting
Formal statement
namespace MICPRep.Periodic
open scoped ENNReal Matrix
/-- Lemma 6.2, p. 22. -/
theorem lemma_6_2 {n p d : ℕ} (M : Set (Ambient n p d)) (S : Set (Pt n))
(hM : IsRationalFormulation M S) (hS : S.Nonempty) (hD : micpDiam M < ⊤)
(hint : (intrinsicInterior ℝ (IZ (indexSet M)) ∩ intLattice d).Nonempty) :
IsBinaryMICPR S ∨ HasNearlyPeriodicFormulation S ∨
∃ d' : ℕ, d = d' + 1 ∧
∃ (p' : ℕ) (Mt : Set (Ambient n p' d')) (St : Set (Pt n)),
IsRationalFormulation Mt St ∧ St.Nonempty ∧ micpDiam Mt ≤ micpDiam M ∧
S ⊆ St ∧ St ⊆ closure St ∧ closure St ⊆ closure S := by sorry
end MICPRep.Periodic
Source
Lubin, Vielma, Zadik, Mixed-integer convex representability, arXiv:1706.05135v3, p. 22, Lemma 6.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.