Integrality of basic solutions of network flow problems
ProvedLinearOptimization.network_flow_integrality(Bertsimas & Tsitsiklis, Theorem 7.5, p. 289, GOAL) Consider an uncapacitated network flow problem and assume that the underlying graph is connected.
- (a) For every basis matrix , the matrix has integer entries.
- (b) If the supplies are integer, then every basic solution has integer coordinates.
- (c) If the cost coefficients are integer, then every dual basic solution has integer coordinates.
(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): .)
import Mathlib.LinearAlgebra.Matrix.NonsingularInverse import Definitions.Def_LinearOptimization_NetworkFlowProblem import Definitions.Def_BasicSolution open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 7.5 (p. 289).** Integrality for the uncapacitated network flow problem `min c'f, Ãf = b̃, f ≥ 0` on a connected graph with `∑ᵢ bᵢ = 0`: (a) every basis matrix of `Ã` has an integer inverse; (b) integer supplies make every basic solution integer; (c) integer costs make every dual basic solution `p' = c_B'B⁻¹` integer. -/
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
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setting: a directed multigraph on the nodes with arcs (ordered tail–head pairs), supplies , costs ; hypotheses: no self-loops, connectivity (either-direction reflexive–transitive closure), and . Let be the truncated incidence matrix (last node's row deleted). A basis is an injection such that the selected columns of are linearly independent in ; the basis matrix is the matrix whose -th column is column of . The conclusion is a conjunction of three claims. (1) For every basis and all indices : the entry of the inverse of the basis matrix equals some integer (formally, equals the real image of some ). The inverse here is the total matrix inverse, whose value on a non-invertible matrix is by convention the zero matrix; under the basis hypothesis the matrix is invertible, but the assertion is literally about this total operation. (2) If every supply value is an integer, then every basic solution of the standard-form system of — all equalities hold ( = truncated supply) and some constraints among the equalities and the sign constraints are active at with linearly independent coefficient vectors — has every coordinate an integer. (3) If every cost is an integer, then for every basis and every satisfying , every coordinate is an integer.
Confirmed by the mission captain (proposal self-audit).