Eq. (2)′ — with positive circuits, Bellman's equations have a unique +∞-or-real solution
ProvedSendSplit.DPEquations.bellman_unique_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 positive cost. Then every or real-valued solution of Bellman's equations
equals the vector of minimum chain costs: for every node (with when no chain exists).
In the proof of Theorem 2 this gives uniqueness of the solution of (2)′ for each fixed , and hence, by induction on , uniqueness in Theorem 2.
Formalization Note Same encoding as the preceding milestone: missing arcs are cost , chains are walks.
Preamble
import Mathlib import Definitions.Def_BertsekasSPGraph import Definitions.Def_SendSplit_DPEquations_Bellman
Formal statement
namespace SendSplit.DPEquations
theorem bellman_unique_solution {V : Type} [Fintype V] [DecidableEq V]
(G : BertsekasSPGraph V)
(hloop : ∀ i, (i, i) ∉ G.arcs) (hout : ∀ j, (G.t, j) ∉ G.arcs)
(hpos : ∀ l, IsSimpleCircuit G l → 0 < circuitLength G l) :
∀ C : V → EReal, IsBellmanSolution G C → ∀ k, C k = 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, Section 3, proof of Theorem 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.