How much flow can be sent from a source to a sink through a network with arc capacities — and what certifies that no more is possible? This mission formalizes §7.4-7.5 of Bertsimas & Tsitsiklis. The circulation calculus of §7.4 supplies the two structural tools: the flow decomposition theorem (Lemma 7.1 — every nonzero nonnegative circulation is a positive combination of simple circulations with only forward arcs, with integer when is integer) and the optimality criterion for the minimum cost network flow problem (Theorem 7.6 — a feasible flow is optimal if and only if there is no unsaturated cycle with negative cost). Section 7.5 then formulates the maximum flow problem ( s.t. , , for , ), defines augmenting paths (Definition 7.2: on forward arcs, on backward arcs) and the Ford–Fulkerson algorithm, and proves integer invariance and finite termination for integer capacities (Theorem 7.8). The goal is Theorem 7.10:
(a) if the Ford–Fulkerson algorithm terminates because no augmenting path can be found, the current flow is optimal;
(b) the value of the maximum flow equals the minimum cut capacity
— the archetypal combinatorial min-max theorem, which the book notes can also be read as LP duality (pp. 311-312).
theorem LinearOptimization.max_flow_min_cut {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) :
(∀ f, IsFeasibleMaxFlow arcs u s t f →
(¬∃ steps, IsAugmentingPath arcs u s t f steps) →
∀ f', IsFeasibleMaxFlow arcs u s t f' →
flowValue arcs s f' ≤ flowValue arcs s f) ∧
maxFlowValue arcs u s t =
⨅ S ∈ {S : Finset (Fin n) | IsCut s t S},
((cutCapacity arcs u S : ℝ≥0∞) : EReal) ∧
(maxFlowValue arcs u s t ≠ ⊤ →
∃ f, IsFeasibleMaxFlow arcs u s t f ∧
((flowValue arcs s f : ℝ) : EReal) = maxFlowValue arcs u s t) := by
sorry
(Bertsimas & Tsitsiklis, Theorem 7.10, p. 310, GOAL)
Encoding: (Part (a) is formalized by its exact mathematical content: a feasible flow admitting no augmenting path is optimal — precisely the Step-3 termination state, and all the book's proof uses. In part (b) both sides may simultaneously be ; the book's proof (p. 311) treats the infinite case explicitly, and in the finite case the maximum is attained, with a minimum-capacity cut given by the labeled set at termination.)
No open leaves. Every sub-goal is proved or awaiting decomposition.