p. 9 — the output family of a generator is a facial description
ProvedKarpPapadimitriou.Generator.facial_from_generatorconvex-hullp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1separation-oracle
Let be a combinatorial optimization problem and a generator that answers every valid rational query as specified. Then its returned inequalities form a facial description:
for each and .
This identifies the exact system of inequalities used by Theorem 2.
Preamble
import Mathlib import Definitions.Def_KarpPapadimitriou_Generator_Oracle
Formal statement
namespace KarpPapadimitriou.Generator
/-- The output family of a generator describes precisely the convex hull. -/
theorem facial_from_generator (C : COP) (gen : Oracle C)
(hgen : IsGenerator C gen) : IsFacialDescription C (FG C gen) := by sorry
end KarpPapadimitriou.Generator
Source
Karp & Papadimitriou, On linear characterizations of combinatorial optimization problems, MIT/LCS/TM-154 (Feb. 1980), p. 9, paragraph defining F_G(C)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.