§2, p. 639 — for each flow,
ProvedSendSplit.Existence.reducedFlowCost_eqnetwork-flowsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1potentials
Let be a graph, arbitrary arc cost functions, and a demand vector. For every flow for ,
where .
Hence the set of flows minimizing does not depend on , and on circulations ; this is how condition 7° yields 4°.
Preamble
import Mathlib import Definitions.Def_SendSplit_Existence_Network import Definitions.Def_SendSplit_Existence_ReducedCost
Formal statement
namespace SendSplit.Existence
theorem reducedFlowCost_eq {n : ℕ} (G : ArcGraph n) (c : Fin n → Fin n → ℝ → ℝ)
(π : Fin n → ℝ) (r : Fin n → ℝ) (x : Fin n → Fin n → ℝ) (hx : IsFlow G r x) :
reducedFlowCost G c π x = flowCost G c x + ∑ i, π i * r i := 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, Section 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.