THEOREM 7 — faces as basic feasible solutions of the integer-point system
ProvedGomory69.MasterFaces.theorem_7basic-feasible-solutionfacetsgroup-polyhedronp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and . The inequality defines a face of if and only if is a basic feasible solution of the system
This characterizes Gomory's faces by the rank of the tight integer-point rows. The system can have infinitely many rows, but only coefficient variables.
Formalization Note. is assumed nonempty (, as on p. 457): for the zero-dimensional coefficient space makes every trivially basic while no nonzero , hence no face, exists.
Preamble
import Mathlib import Definitions.Def_Gomory69_MasterFaces_BasicFeasible
Formal statement
namespace Gomory69.MasterFaces
/-- Gomory (1969), THEOREM 7, pp. 469–470. `N` is nonempty (`n′ ≥ 1`, p. 457): at
`N = ∅` the tight-row span is trivially full while no face exists. -/
theorem theorem_7 {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G]
(N : Finset G) (hN : (0 : G) ∉ N) (hNne : N.Nonempty) (g₀ : G) (π : N → ℝ) (π₀ : ℝ)
(hπ₀ : 0 < π₀) :
IsFace N g₀ π π₀ ↔ IsTBasicFeasible N g₀ π₀ π := by sorry
end Gomory69.MasterFaces
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), pp. 469–470, THEOREM 7. DOI: 10.1016/0024-3795(69)90017-2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.