Eq. (15.8) — flow value is at most the capacity of any cut
ProvedVanderbeiLP.Networks.flow_le_cut_capacitylinear-programmingmax-flownetwork-flowsp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1
In the maximum-flow problem on a network with source , sink and upper bounds , let be a feasible flow and a cut (, ). Then
This is the weak-duality half of the Max-Flow Min-Cut Theorem 15.1; the book obtains it from the flow-balance identity (15.7).
Preamble
import Mathlib import Definitions.Def_VanderbeiLP_Networks_MaxFlow
Formal statement
namespace VanderbeiLP.Networks
/-- **Eq. (15.8)** (Vanderbei, *Linear Programming*, 4th ed., p. 234). In the maximum-flow
problem, `x_{ts} ≤ κ(C)` for every feasible flow and every cut set `C`. -/
theorem flow_le_cut_capacity {N : Type*} [Fintype N] [DecidableEq N]
(A : Finset (N × N)) (hA : IsNetwork A) (u : N × N → ℝ) (s t : N)
(x : N × N → ℝ) (xts : ℝ) (hx : IsMaxFlowFeasible A u s t x xts)
(C : Finset N) (hC : IsCut s t C) :
xts ≤ cutCapacity A u C := by sorry
end VanderbeiLP.Networks
Source
Vanderbei, Linear Programming: Foundations and Extensions, 4th ed., Springer 2014, p. 234 (PDF 245), Eq. (15.8) in the proof of Theorem 15.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.