Proof of Theorem 1, p. 639 — for all iff
ProvedSendSplit.Existence.simpleCirculation_cost_nonneg_iffconcave-costnetwork-flowsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a graph with arc costs concave on and , and let be a simple circulation whose induced subgraph is the simple circuit with arc set . Then
where the right-hand sum is taken in .
This is the circuit-by-circuit form of the equivalence of 4° and 5° in Theorem 1.
Formalization Note is slopeAtInfty (c i j) (see the AugmentedGraph definition), an EReal; the sum is an EReal sum of values that are never .
Preamble
import Mathlib import Definitions.Def_SendSplit_Existence_Network import Definitions.Def_SendSplit_Existence_AugmentedGraph
Formal statement
namespace SendSplit.Existence
theorem simpleCirculation_cost_nonneg_iff {n : ℕ} (G : ArcGraph n) (c : Fin n → Fin n → ℝ → ℝ)
(hc : IsConcaveArcCost G c) (y : Fin n → Fin n → ℝ) (hy : IsSimpleCirculation G y) :
(∀ θ : ℝ, 0 ≤ θ → 0 ≤ flowCost G c (fun i j => θ * y i j)) ↔
0 ≤ ∑ p ∈ support G y, slopeAtInfty (c p.1 p.2) := by sorry
end SendSplit.Existence
Source
Erickson, Monma, Veinott, Send-and-Split Method for Minimum-Concave-Cost Network Flows, Math. Oper. Res. 12 (1987), p. 639, proof of Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.