p. 8, proof of Theorem 1, (ii)⇔(iii) — the hull may be replaced by the system f·x ≤ g, ⟨z,f,g⟩ ∈ F(C)
ProvedKarpPapadimitriou.Facial.lt_on_hull_iff_lt_on_systemlinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedral-combinatorics
Let be a combinatorial optimization problem, a facial description of , , and . Then the following are equivalent:
(ii) the program subject to has optimal value ;
(iii) the program
has optimal value .
Here both are read as "every feasible has ". The step is the point where the facial description enters the proof of Theorem 1.
Formalization Note As in step (i)⇔(ii), "optimal value " means that every feasible point has value .
Preamble
import Mathlib import Definitions.Def_KarpPapadimitriou_Facial_FacialDescription
Formal statement
namespace KarpPapadimitriou.Facial
theorem lt_on_hull_iff_lt_on_system (C : COP) (F : Triples C) (hF : IsFacialDescription C F)
(z : List Bool) (hz : z ∈ C.L) (c : Fin (C.n z) → ℤ) (k : ℤ) :
(∀ x ∈ hull C z, (fun j => (c j : ℚ)) ⬝ᵥ x < (k : ℚ)) ↔
∀ x : Fin (C.n z) → ℚ,
(∀ (f : Fin (C.n z) → ℤ) (g : ℤ),
(⟨z, (f, g)⟩ : Σ z : List Bool, (Fin (C.n z) → ℤ) × ℤ) ∈ F →
(fun j => (f j : ℚ)) ⬝ᵥ x ≤ (g : ℚ)) →
(fun j => (c j : ℚ)) ⬝ᵥ x < (k : ℚ) := by sorry
end KarpPapadimitriou.Facial
Source
Karp & Papadimitriou, On linear characterizations of combinatorial optimization problems, MIT/LCS/TM-154 (Feb. 1980), p. 8, proof of Theorem 1, (ii)⇔(iii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.