Eq. (5) — C_iI ≤ c_ij(r_I) + C_jI for every (i, j) ∈ A_I
ProvedSendSplit.DPEquations.eq5_send_ledynamic-programmingnetwork-flowsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
In the network model with arc costs concave on and vanishing at , let and let (so ). Then
where when . Sending along the arc from to and then solving the subproblem gives a flow for the subproblem . If the inequality is trivial.
Formalization Note The page derives (5) inside the case " finite" of the proof of Theorem 2; the inequality holds without that supposition and without the existence of a minimum-cost flow, so neither is a hypothesis. Extended-real addition of a real number and is well defined in every case.
Preamble
import Mathlib import Definitions.Def_SendSplit_DPEquations_Network import Definitions.Def_SendSplit_DPEquations_Subproblem import Definitions.Def_SendSplit_DPEquations_Equations
Formal statement
namespace SendSplit.DPEquations
theorem eq5_send_le {n : ℕ} (A : Finset (Fin n × Fin n))
(c : Fin n → Fin n → ℝ → ℝ) (r : Fin n → ℝ)
(hA : IsGraph A) (hc : IsConcaveArcCost A c)
(i j : Fin n) (I : Finset (Fin n)) (hI : IsAdmissible r I)
(hij : IsSendArc A r I i j) :
minCost A c r i I ≤ sendCost A c r I i j + minCost A c r j I := 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. (5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.