Proposition 4.2, pp. 10–11 — binary MICP-R sets are exactly finite unions of projections of nonempty closed convex sets, via the lifted formulation (4.4)
ProvedMICPRep.Periodic.proposition_4_2Let . Then is binary MICP-R if and only if there are , and nonempty closed convex sets such that
Moreover, for any such sets the closed convex set
induces an MICP formulation of (with continuous variables) and every point of with integer has , so the formulation is binary.
The proposition removes the equal-recession-cone restriction of Jeroslow's characterization by one continuous lifting variable; it is how the main theorem's proof rewrites the binary part of its decomposition as a finite union of convex sets.
Formalization Note The number of sets is existential and is unrelated to the number of integer variables of a given binary formulation of ; in (4.4) the formulation built has exactly integer variables. The squared norm of is . The set is the module liftedHull.
import Mathlib import Definitions.Def_MICPRep_Periodic_Setting
namespace MICPRep.Periodic
open scoped ENNReal Matrix
/-- Proposition 4.2, pp. 10–11. -/
theorem proposition_4_2 {n : ℕ} (S : Set (Pt n)) :
(IsBinaryMICPR S ↔
∃ (q k : ℕ) (St : Fin k → Set (Pt n × (Fin q → ℝ))),
(∀ i, (St i).Nonempty ∧ IsClosed (St i) ∧ Convex ℝ (St i)) ∧
S = ⋃ i, Prod.fst '' St i) ∧
∀ (q k : ℕ) (St : Fin k → Set (Pt n × (Fin q → ℝ))),
(∀ i, (St i).Nonempty ∧ IsClosed (St i) ∧ Convex ℝ (St i)) →
S = ⋃ i, Prod.fst '' St i →
Induces (liftedHull St) S ∧
∀ v ∈ liftedHull St, v.2.2 ∈ intLattice k → ∀ i : Fin k, v.2.2 i = 0 ∨ v.2.2 i = 1 := by sorry
end MICPRep.Periodic
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.