Theorem 2 (Dynamic-Programming Equations) — C is the greatest +∞-or-real solution of (1) and (2), and the only one if simple circulations cost positively
ProvedSendSplit.DPEquations.theorem2_dp_equationsTheorem 2 (Dynamic-Programming Equations). Let be a network whose arc costs are concave on with , and let , , , be the array of subproblem minimum costs. If there is a minimum-cost flow for , then is the greatest or real-valued solution of (1) and (2) (with defined by (3)):
- is a or real-valued solution of (1) and (2);
- every or real-valued solution of (1) and (2) satisfies
If moreover each simple circulation has positive cost, then is the only such solution: every or real-valued solution of (1) and (2) equals on all and .
In particular the minimum cost of the original problem, , is determined by the equations. Without the positivity hypothesis uniqueness can fail: if every , for all nonempty proper subsets of , and is strongly connected, then while also solves (1) and (2) (p. 641).
Formalization Note "+∞ or real-valued" is the condition on every admissible ; for it is part of the first conclusion. "Greatest" is stated as two claims, that is a solution and that it dominates every solution. "Each simple circulation has positive cost" quantifies over every simple circuit and every flow value on it. Arrays are compared only on .
import Mathlib import Definitions.Def_SendSplit_DPEquations_Network import Definitions.Def_SendSplit_DPEquations_Subproblem import Definitions.Def_SendSplit_DPEquations_Equations
namespace SendSplit.DPEquations
theorem theorem2_dp_equations {n : ℕ} (A : Finset (Fin n × Fin n))
(c : Fin n → Fin n → ℝ → ℝ) (r : Fin n → ℝ)
(hA : IsGraph A) (hc : IsConcaveArcCost A c)
(hmin : ∃ x, IsMinCostFlow A c r x) :
IsSolution A c r (minCost A c r) ∧
(∀ C' : Fin n → Finset (Fin n) → EReal, IsSolution A c r C' →
∀ j I, IsAdmissible r I → C' j I ≤ minCost A c r j I) ∧
((∀ y, IsSimpleCirculation A y → 0 < flowCost A c y) →
∀ C' : Fin n → Finset (Fin n) → EReal, IsSolution A c r C' →
∀ j I, IsAdmissible r I → C' j I = minCost A c r j I) := by sorry
end SendSplit.DPEquations
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.