Proof of Theorem 1, p. 639 —
ProvedSendSplit.Existence.concave_sandwichconcave-costnetwork-flowsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a graph with arc costs concave on and . For all preflows and every ,
The left inequality is concavity of at the midpoint of and ; the right one is subadditivity, which follows from concavity and . With it, is bounded below in if and only if is.
Formalization Note The paper states the display for an extreme flow and a simple circulation ; it holds for all preflows, and this general form is stated.
Preamble
import Mathlib import Definitions.Def_SendSplit_Existence_Network
Formal statement
namespace SendSplit.Existence
theorem concave_sandwich {n : ℕ} (G : ArcGraph n) (c : Fin n → Fin n → ℝ → ℝ)
(hc : IsConcaveArcCost G c) (x y : Fin n → Fin n → ℝ) (hx : IsPreflow G x)
(hy : IsPreflow G y) (θ : ℝ) (hθ : 0 ≤ θ) :
(1 / 2 : ℝ) * flowCost G c (fun i j => 2 * x i j)
+ (1 / 2 : ℝ) * flowCost G c (fun i j => 2 * (θ * y i j))
≤ flowCost G c (fun i j => x i j + θ * y i j) ∧
flowCost G c (fun i j => x i j + θ * y i j)
≤ flowCost G c x + flowCost G c (fun i j => θ * y i j) := 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.