THEOREM 17 — equalities and subadditivity for master faces
ProvedGomory69.MasterFaces.theorem_17facetsgroup-polyhedronp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1subadditivity
Let and let be a face of the master polyhedron with . With , its coefficients satisfy all three conditions:
These are the face-implied rows of system (13). In the first line, uses the zero extension and repeats the last equality.
Preamble
import Mathlib import Definitions.Def_Gomory69_MasterFaces_GroupPolyhedron
Formal statement
namespace Gomory69.MasterFaces
/-- Gomory (1969), THEOREM 17, pp. 480–481; `π(0) = 0` by extension. -/
theorem theorem_17 {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G]
(g₀ : G) (hg₀ : g₀ ≠ 0) (π : MasterIndex G → ℝ) (π₀ : ℝ)
(hπ₀ : 0 < π₀) (hface : IsFace (masterSupport G) g₀ π π₀) :
(∀ g : MasterIndex G,
extendZero π (g : G) + extendZero π (g₀ - (g : G)) = π₀) ∧
(∀ g h : MasterIndex G,
extendZero π ((g : G) + (h : G)) ≤ π g + π h) ∧
extendZero π g₀ = π₀ := by sorry
end Gomory69.MasterFaces
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), pp. 480–481, THEOREM 17 and preceding positive-constant context. DOI: 10.1016/0024-3795(69)90017-2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.