Integrality and finite termination of the Ford–Fulkerson algorithm
ProvedLinearOptimization.max_flow_ford_fulkerson_integer_terminationford-fulkersonintegralitymax-flownetwork-flows
(Bertsimas & Tsitsiklis, Theorem 7.8, p. 305) Suppose that all arc capacities are integer or infinite, and that the Ford–Fulkerson algorithm is initialized with an integer flow vector.
Then, the arc flow variables remain integer throughout the algorithm and, if the optimal value is finite, the algorithm terminates after a finite number of steps.
Encoding: (Formalized over the run predicate: every flow in every admissible Ford–Fulkerson run started at an integer feasible flow is integer, and if the maximum flow value is finite, there is no infinite admissible run — for every augmenting-path selection rule.)
Preamble
import Definitions.Def_LinearOptimization_AugmentingPath open Matrix open scoped ENNReal /-- **Bertsimas & Tsitsiklis, Theorem 7.8 (p. 305).** For integer-or-infinite capacities and an integer initial feasible flow: every flow produced by the Ford–Fulkerson algorithm is integer, and if the maximum flow value is finite there is no infinite admissible run — under every augmenting-path selection rule. -/
Formal statement
theorem LinearOptimization.max_flow_ford_fulkerson_integer_termination {n m : ℕ}
(arcs : Fin m → Fin n × Fin n) (u : Fin m → ℝ≥0∞) (s t : Fin n)
(hst : s ≠ t) (hloop : HasNoSelfLoops arcs) (hupos : ∀ k, 0 < u k)
(huint : ∀ k, u k = ⊤ ∨ ∃ z : ℕ, u k = (z : ℝ≥0∞))
(f₀ : Fin m → ℝ) (hf₀ : IsFeasibleMaxFlow arcs u s t f₀)
(hint₀ : ∀ k, ∃ z : ℤ, f₀ k = (z : ℝ)) :
(∀ f, Relation.ReflTransGen (IsFordFulkersonStep arcs u s t) f₀ f →
∀ k, ∃ z : ℤ, f k = (z : ℝ)) ∧
(maxFlowValue arcs u s t ≠ ⊤ →
¬∃ g : ℕ → Fin m → ℝ, g 0 = f₀ ∧
∀ i, IsFordFulkersonStep arcs u s t (g i) (g (i + 1))) := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 7.8, p. 305