Eq. (4) — C_iI ≤ c(x) + c(y) whenever x + y is a flow for the subproblem i → I
ProvedSendSplit.DPEquations.eq4_subadditiveconcave-costnetwork-flowsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
In the network model with arc costs concave on and vanishing at , let and . If and are preflows such that is a flow for the subproblem , then
It combines with the subadditivity of the flow cost, and is the common step behind (5) and (6).
Formalization Note The paper states (4) under the standing supposition " is finite"; the inequality is true without it, so that supposition is not a hypothesis here.
Preamble
import Mathlib import Definitions.Def_SendSplit_DPEquations_Network import Definitions.Def_SendSplit_DPEquations_Subproblem
Formal statement
namespace SendSplit.DPEquations
theorem eq4_subadditive {n : ℕ} (A : Finset (Fin n × Fin n))
(c : Fin n → Fin n → ℝ → ℝ) (r : Fin n → ℝ)
(hA : IsGraph A) (hc : IsConcaveArcCost A c)
(i : Fin n) (I : Finset (Fin n)) (hI : IsAdmissible r I)
(x y : Fin n → Fin n → ℝ) (hx : IsPreflow A x) (hy : IsPreflow A y)
(hxy : IsFlow A (subDemand r i I) (x + y)) :
minCost A c r i I ≤ ((flowCost A c x + flowCost A c y : ℝ) : EReal) := by sorry
end SendSplit.DPEquations
Source
Erickson, Monma, Veinott, Send-and-Split Method for Minimum-Concave-Cost Network Flows, Math. Oper. Res. 12 (1987), p. 641, Eq. (4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.