§2, p. 638 — extension of Hirsch–Hoffman: c attains its minimum on the flows iff it is bounded below on each extreme ray; then at an extreme flow
ProvedSendSplit.Existence.hirsch_hoffman_extensionLet be a graph with arc costs concave on and , and let be a demand vector for which the set of flows is nonempty. Then the flow cost attains its minimum on the set of flows for if and only if, for every extreme flow for and every simple circulation , the function
is bounded below. Moreover, if a minimum-cost flow for exists, then some extreme flow is a minimum-cost flow for .
The extreme flows are the extreme points and the simple circulations the extreme directions of recession of the polyhedron of flows, so this is the extension of the Hirsch–Hoffman theorem on concave minimization over polyhedra that the paper invokes. It is the step that turns 4° into 1° and 3°.
Formalization Note "Bounded below on each half-line" is the explicit statement ; "assumes its minimum" is the existence of a minimum-cost flow.
import Mathlib import Definitions.Def_SendSplit_Existence_Network
namespace SendSplit.Existence
theorem hirsch_hoffman_extension {n : ℕ} (G : ArcGraph n) (c : Fin n → Fin n → ℝ → ℝ)
(hc : IsConcaveArcCost G c) (r : Fin n → ℝ) (hflow : ∃ x, IsFlow G r x) :
((∃ x, IsMinCostFlow G c r x) ↔
∀ x, IsExtremeFlow G r x → ∀ y, IsSimpleCirculation G y →
∃ M : ℝ, ∀ θ : ℝ, 0 ≤ θ → M ≤ flowCost G c (fun i j => x i j + θ * y i j)) ∧
((∃ x, IsMinCostFlow G c r x) → ∃ x, IsMinCostFlow G c r x ∧ IsExtremeFlow G r x) := by sorry
end SendSplit.Existence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.