THEOREM 18 — master faces are basic solutions of system (13)
ProvedGomory69.MasterFaces.theorem_18basic-feasible-solutionfacetsgroup-polyhedronp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1subadditivity
Let be a finite Abelian group, , and . An inequality defines a face of the master polyhedron if and only if is a basic feasible solution of system (13):
The theorem replaces the infinite integer-point description of faces by a finite system of equations and subadditive inequalities. Both directions of the equivalence are part of the target.
Formalization Note A face is a facet generated by tight integer points. Basicness means that tight row coefficient vectors span the full variable space. The system includes ordered pairs and ; , is fixed, and the zero right-hand side is excluded.
Preamble
import Mathlib import Definitions.Def_Gomory69_MasterFaces_BasicFeasible
Formal statement
namespace Gomory69.MasterFaces
/-- Gomory (1969), THEOREM 18, pp. 481–483. -/
theorem theorem_18 {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G]
(g₀ : G) (hg₀ : g₀ ≠ 0) (π : MasterIndex G → ℝ) (π₀ : ℝ)
(hπ₀ : 0 < π₀) :
IsFace (masterSupport G) g₀ π π₀ ↔ IsSystem13Basic g₀ π₀ π := by sorry
end Gomory69.MasterFaces
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), pp. 481–483, THEOREM 18 and system (13). DOI: 10.1016/0024-3795(69)90017-2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.