Why do network linear programs return integer answers for free? This mission formalizes the structural theory of the minimum cost network flow problem of Chapter 7 of Bertsimas & Tsitsiklis: a directed graph with external supplies , arc costs , and the node-arc incidence matrix — an matrix in which every column has exactly one (start node) and one (end node) — so that flow conservation reads , forcing the standing assumption . Because the rows of sum to zero, the book works with the truncated matrix of the first rows. The combinatorial heart is the correspondence between algebra and graph structure: a set of arcs forming a tree determines a unique tree solution of , off (Theorem 7.3); connectedness makes full-rank (Corollary 7.1); and a flow vector is a basic solution if and only if it is a tree solution (Theorem 7.4). The goal theorem is the integrality theorem (Theorem 7.5): for the uncapacitated problem on a connected graph, every basis matrix has an integer inverse (its determinant is by the tree/lower-triangular argument), integer supplies make every basic solution integer, and integer costs make every dual basic solution integer — whence integer optimal primal and dual solutions exist whenever the optimal cost is finite (Corollary 7.2). This is the fountainhead of combinatorial integrality in linear optimization, feeding the max-flow min-cut mission that follows.
theorem LinearOptimization.network_flow_integrality {n m : ℕ}
(arcs : Fin m → Fin (n + 1) × Fin (n + 1)) (bsupply : Fin (n + 1) → ℝ)
(cost : Fin m → ℝ)
(hloop : HasNoSelfLoops arcs) (hconn : IsConnectedNetwork arcs)
(hsum : ∑ i, bsupply i = 0) :
(∀ B : Fin n ↪ Fin m, IsStdBasis (truncatedIncidence arcs) B →
∀ i j, ∃ z : ℤ, (basisMatrix (truncatedIncidence arcs) B)⁻¹ i j = (z : ℝ)) ∧
((∀ i, ∃ z : ℤ, bsupply i = (z : ℝ)) →
∀ f, IsBasicSolution
(stdFormSystem (truncatedIncidence arcs) (truncatedSupply bsupply)) f →
∀ k, ∃ z : ℤ, f k = (z : ℝ)) ∧
((∀ k, ∃ z : ℤ, cost k = (z : ℝ)) →
∀ B : Fin n ↪ Fin m, IsStdBasis (truncatedIncidence arcs) B →
∀ p : Fin n → ℝ,
(basisMatrix (truncatedIncidence arcs) B)ᵀ.mulVec p =
(fun i => cost (B i)) →
∀ i, ∃ z : ℤ, p i = (z : ℝ)) := by
sorry
(Bertsimas & Tsitsiklis, Theorem 7.5, p. 289, GOAL) Consider an uncapacitated network flow problem and assume that the underlying graph is connected.
(Basis matrices are the nonsingular submatrices of formed by the columns of the arcs of a tree, cf. Theorems 7.3-7.4; basic solutions satisfy , dual basic solutions , p. 289. Standing Assumption 7.1(a): .)
No open leaves. Every sub-goal is proved or awaiting decomposition.