Lemma 6.13, p. 30 — each integer recession direction r gives a unique asymptotic direction u, and for u = 0 the unions along z + rℝ₊ are convex with diameter at most D_MICP(M)
ProvedMICPRep.Periodic.lemma_6_13convex-analysismixed-integer-convex-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1periodic-set
Let be closed and convex, inducing a rational MICP formulation with index set and -projected sets . Assume and has an integer point in its relative interior. Then for every there is a unique with
Furthermore, if , then for every the set is convex, , and
Either the recession direction produces a nearly periodic formulation () or the integer variable along can be relaxed without increasing the diameter (); this is the dichotomy behind Lemma 6.2.
Formalization Note ranges over the reals, , and diameters are extended (Metric.ediam). "If " is stated as: for every satisfying (6.26), if then the conclusions hold.
Preamble
import Mathlib import Definitions.Def_MICPRep_Periodic_Setting
Formal statement
namespace MICPRep.Periodic
open scoped ENNReal Matrix
/-- Lemma 6.13, p. 30. -/
theorem lemma_6_13 {n p d : ℕ} (M : Set (Ambient n p d)) (S : Set (Pt n))
(hM : IsRationalFormulation M S) (hD : micpDiam M < ⊤)
(hint : (intrinsicInterior ℝ (IZ (indexSet M)) ∩ intLattice d).Nonempty)
(r : Fin d → ℝ) (hrZ : r ∈ intLattice d) (hrI : r ∈ recCone (indexSet M)) (hr0 : r ≠ 0) :
(∃! u : Pt n, ∀ t : ℝ, 0 < t → ∀ z ∈ intLattice d ∩ indexSet M, ∀ x ∈ zProj M z,
x + t • u ∈ closure (zProj M (z + t • r))) ∧
∀ u : Pt n, (∀ t : ℝ, 0 < t → ∀ z ∈ intLattice d ∩ indexSet M, ∀ x ∈ zProj M z,
x + t • u ∈ closure (zProj M (z + t • r))) → u = 0 →
∀ z ∈ intLattice d ∩ indexSet M,
Convex ℝ (⋃ z' ∈ {w | ∃ t : ℝ, 0 ≤ t ∧ w = z + t • r}, zProj M z') ∧
Metric.ediam (⋃ z' ∈ {w | ∃ t : ℝ, 0 ≤ t ∧ w = z + t • r}, zProj M z') ≤ micpDiam M ∧
(⋃ z' ∈ {w | ∃ t : ℝ, 0 ≤ t ∧ w = z + t • r} ∩ intLattice d, zProj M z') ⊆
(⋃ z' ∈ {w | ∃ t : ℝ, 0 ≤ t ∧ w = z + t • r}, zProj M z') ∧
(⋃ z' ∈ {w | ∃ t : ℝ, 0 ≤ t ∧ w = z + t • r}, zProj M z') ⊆
⋃ z' ∈ {w | ∃ t : ℝ, 0 ≤ t ∧ w = z + t • r} ∩ intLattice d,
closure (zProj M z') := by sorry
end MICPRep.Periodic
Source
Lubin, Vielma, Zadik, Mixed-integer convex representability, arXiv:1706.05135v3, p. 30, Lemma 6.13 and (6.26)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.