Eq. (2)′ — with nonnegative circuits, minimum chain costs are the greatest +∞-or-real solution of Bellman's equations, nondecreasing in the arc costs
ProvedSendSplit.DPEquations.bellman_greatest_solutiondynamic-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1shortest-paths
Let be a finite directed graph without loops, with real arc costs on its arcs and a destination node from which no arc leaves. Suppose that every simple circuit of has nonnegative cost. For each node let
with if there is no such chain. Then:
- is a or real-valued solution of Bellman's equations , for ;
- is the minimum cost among all chains from to : either or some chain from to has cost exactly ;
- is the greatest such solution: for every or real-valued solution and every ;
- is nondecreasing in the arc costs: if has the same destination, its arcs are among those of , and on every arc of , then for all .
In the proof of Theorem 2 this is applied to , where (2) becomes (2)′; item 4 is what transfers to .
Formalization Note Arc costs in are encoded by real lengths on an arc set: a cost of is a missing arc. Hence "" for extended costs becomes: every arc of is an arc of , with no larger cost. Chains are walks (nodes may repeat), as in the platform definition BertsekasShortestDistance; the paper's "as is well known" is made explicit as items 1–4.
Preamble
import Mathlib import Definitions.Def_BertsekasSPGraph import Definitions.Def_SendSplit_DPEquations_Bellman
Formal statement
namespace SendSplit.DPEquations
theorem bellman_greatest_solution {V : Type} [Fintype V] [DecidableEq V]
(G : BertsekasSPGraph V)
(hloop : ∀ i, (i, i) ∉ G.arcs) (hout : ∀ j, (G.t, j) ∉ G.arcs)
(hcirc : ∀ l, IsSimpleCircuit G l → 0 ≤ circuitLength G l) :
IsBellmanSolution G (fun k => BertsekasShortestDistance G k G.t) ∧
(∀ k, BertsekasShortestDistance G k G.t = ⊤ ∨
∃ l, BertsekasIsWalkFrom G k G.t l ∧
((BertsekasWalkLength G l : ℝ) : EReal) = BertsekasShortestDistance G k G.t) ∧
(∀ C : V → EReal, IsBellmanSolution G C → ∀ k, C k ≤ BertsekasShortestDistance G k G.t) ∧
(∀ G' : BertsekasSPGraph V, G'.t = G.t → G'.arcs ⊆ G.arcs →
(∀ p ∈ G'.arcs, G.length p.1 p.2 ≤ G'.length p.1 p.2) →
∀ k, BertsekasShortestDistance G k G.t ≤ BertsekasShortestDistance G' k G'.t) := 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. 642, Eq. (2)′
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.