Lemma 6.6, p. 25 — a rational affine change of the integer variables keeps a rational MICP formulation and does not increase D_MICP
ProvedMICPRep.Periodic.lemma_6_6mixed-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 with index set and -projected sets . Let be an invertible rational affine map with , and
Then is closed and convex, induces a rational MICP formulation of
with index set , and . If in addition , then and .
The lemma lets the proof rearrange the index set by unimodular and slicing maps without loss of generality.
Formalization Note ratAff A b with invertible and ratAffInv A b; is written as the preimage of under .
Preamble
import Mathlib import Definitions.Def_MICPRep_Periodic_Setting
Formal statement
namespace MICPRep.Periodic
open scoped ENNReal Matrix
/-- Lemma 6.6, p. 25. -/
theorem lemma_6_6 {n p d : ℕ} (M : Set (Ambient n p d)) (S : Set (Pt n))
(hM : IsRationalFormulation M S) (A : Matrix (Fin d) (Fin d) ℚ) (b : Fin d → ℚ)
(hA : IsUnit A) (hpre : ratAff A b ⁻¹' intLattice d ⊆ intLattice d) :
let M' : Set (Ambient n p d) := {q | (q.1, q.2.1, ratAffInv A b q.2.2) ∈ M}
let S' : Set (Pt n) :=
⋃ z' ∈ ratAff A b '' indexSet M ∩ intLattice d, zProj M (ratAffInv A b z')
IsRationalFormulation M' S' ∧ indexSet M' = ratAff A b '' indexSet M ∧
micpDiam M' ≤ micpDiam M ∧
(ratAff A b '' intLattice d = intLattice d →
ratAff A b ⁻¹' intLattice d = intLattice d →
S' = S ∧ micpDiam M = micpDiam M') := by sorry
end MICPRep.Periodic
Source
Lubin, Vielma, Zadik, Mixed-integer convex representability, arXiv:1706.05135v3, p. 25, Lemma 6.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.