Eq. (1) — if r_I = 0 then C_iI = C_{j,I∖{j}} for every j ∈ I
ProvedSendSplit.DPEquations.eq1_zero_demanddynamic-programmingnetwork-flowsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
In the network model with concave arc costs vanishing at , let and with . Then for every , writing ,
This is equation (1) of the send-and-split method: when the demands in balance, the subproblem does not depend on the node at which is subtracted. With it gives the observation of p. 640 that the minimum cost of the original problem is .
Preamble
import Mathlib import Definitions.Def_SendSplit_DPEquations_Network import Definitions.Def_SendSplit_DPEquations_Subproblem
Formal statement
namespace SendSplit.DPEquations
theorem eq1_zero_demand {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) (hrI : demandSum r I = 0)
(j : Fin n) (hj : j ∈ I) :
minCost A c r i I = minCost A c r j (I.erase j) := 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. 640, Eq. (1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.