p. 5 — a small facial description makes every CH(S(z)) a convex polyhedron
ProvedKarpPapadimitriou.Facial.hull_isPolyhedron_of_smallconvex-hullp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedral-combinatorics
Let be a combinatorial optimization problem and a small facial description of . Then for every :
- only finitely many triples of have first entry ;
- is a convex polyhedron, i.e. there are finitely many pairs with
This is the remark that follows the definition of small facial descriptions: smallness bounds the coefficients, so only finitely many inequalities can be listed for each input, and the convex hull is the intersection of finitely many half-spaces.
Formalization Note Part 1 is the reason the paper's remark holds and is stated explicitly. A half-space is written with rational data; gives the whole space.
Preamble
import Mathlib import Definitions.Def_KarpPapadimitriou_Facial_FacialDescription
Formal statement
namespace KarpPapadimitriou.Facial
theorem hull_isPolyhedron_of_small (C : COP) (F : Triples C)
(hF : IsFacialDescription C F) (hs : IsSmall C F) (z : List Bool) (hz : z ∈ C.L) :
{fg : (Fin (C.n z) → ℤ) × ℤ |
(⟨z, fg⟩ : Σ z : List Bool, (Fin (C.n z) → ℤ) × ℤ) ∈ F}.Finite ∧
∃ H : Finset ((Fin (C.n z) → ℚ) × ℚ),
hull C z = {x : Fin (C.n z) → ℚ | ∀ h ∈ H, h.1 ⬝ᵥ x ≤ h.2} := by sorry
end KarpPapadimitriou.Facial
Source
Karp & Papadimitriou, On linear characterizations of combinatorial optimization problems, MIT/LCS/TM-154 (Feb. 1980), p. 5, remark after the definition of small facial descriptions
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.