Proof of Theorem 1, p. 639 — under 6°: on flows and
ProvedSendSplit.Existence.six_implies_seven_boundsconcave-costnetwork-flowsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1shortest-paths
Let be a graph with arc costs concave on and , let be a demand vector and . Let contain exactly one node of each sink strong component of and no other node, and let be the arc costs of the augmented graph : on arcs inside strong components, a real on arcs of joining distinct strong components, a real on the appended arcs . Assume
- for every arc joining distinct strong components, and
- (condition 6°) from every node of there is a minimum-cost chain to under .
Then for every flow for and every arc of ; every minimum chain cost is a real number; and
Together these give 7° with .
Formalization Note The products and the inequality are stated in EReal, so that no EReal subtraction occurs; with real this is the paper's inequality. The hypothesis 6° is assumed for the given and only.
Preamble
import Mathlib import Definitions.Def_SendSplit_Existence_Network import Definitions.Def_SendSplit_Existence_AugmentedGraph
Formal statement
namespace SendSplit.Existence
theorem six_implies_seven_bounds {n : ℕ} (G : ArcGraph n) (c : Fin n → Fin n → ℝ → ℝ)
(hc : IsConcaveArcCost G c) (r : Fin n → ℝ) (S : Finset (Fin n))
(hS : IsSinkSelection G S) (b : Fin n → Fin n → ℝ) (bν : Fin n → ℝ)
(hext : ∀ p ∈ G.A, ¬ SameComponent G p.1 p.2 →
b p.1 p.2 * (∑ i, max (r i) 0) ≤ c p.1 p.2 (∑ i, max (r i) 0))
(h6 : ∀ u, HasMinCostChain G S (augCost G c b bν) u) :
(∀ x, IsFlow G r x → ∀ p ∈ G.A,
augCost G c b bν (some p.1) (some p.2) * ((x p.1 p.2 : ℝ) : EReal)
≤ ((c p.1 p.2 (x p.1 p.2) : ℝ) : EReal)) ∧
(∀ i, minChainCost G S (augCost G c b bν) i ≠ ⊥ ∧
minChainCost G S (augCost G c b bν) i ≠ ⊤) ∧
∀ p ∈ G.A, minChainCost G S (augCost G c b bν) p.1
≤ augCost G c b bν (some p.1) (some p.2) + minChainCost G S (augCost G c b bν) 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 (6° implies 7°)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.