p. 8, proof of Theorem 1, (iii)⇔(vi) — a nonsingular n(z)×n(z) row selection of F(C) certifies optimal value < k
ProvedKarpPapadimitriou.Facial.lt_on_system_iff_basic_dualLet be a combinatorial optimization problem, a small facial description of , and with . Let and . Then the following are equivalent:
(iii) the program subject to for all has optimal value , i.e. every feasible has ;
(vi) there exist an integer matrix and an integer vector such that
is nonsingular, and the (therefore unique) solution of the system
is nonnegative and satisfies .
In the paper this equivalence passes through (iv) "the dual of program (I) has optimal value " and (v) "the dual of program (I) has a basic feasible solution of value "; condition (vi) is the explicit form of (v), a basic dual solution supported on linearly independent inequalities. It is the short certificate that Algorithm B guesses to recognize the complement of .
Formalization Note The hypothesis is tacit in the paper's proof and is needed: for and the description of the empty hull, and satisfy (iii) (vacuously), while the only nonsingular selection with a nonnegative solution of is the row , with and . "Unique solution" is formalized as nonsingularity of (determinant ), which is how Algorithm B (step (iv)) checks it. Intermediate conditions (iv) and (v) are not stated separately.
import Mathlib import Definitions.Def_KarpPapadimitriou_Facial_FacialDescription
namespace KarpPapadimitriou.Facial
theorem lt_on_system_iff_basic_dual (C : COP) (F : Triples C) (hF : IsFacialDescription C F)
(hs : IsSmall C F) (z : List Bool) (hz : z ∈ C.L) (hS : (C.S z).Nonempty)
(c : Fin (C.n z) → ℤ) (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 : ℚ)) ↔
∃ (fm : Matrix (Fin (C.n z)) (Fin (C.n z)) ℤ) (g : Fin (C.n z) → ℤ),
(∀ i, (⟨z, (fm i, g i)⟩ : Σ z : List Bool, (Fin (C.n z) → ℤ) × ℤ) ∈ F) ∧
fm.det ≠ 0 ∧
∃ y : Fin (C.n z) → ℚ,
Matrix.vecMul y (fm.map (fun a : ℤ => (a : ℚ))) = (fun j => (c j : ℚ)) ∧
0 ≤ y ∧ y ⬝ᵥ (fun i => (g i : ℚ)) < (k : ℚ) := by sorry
end KarpPapadimitriou.Facial
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.