Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Integrality of basic solutions of network flow problems

Proved
LinearOptimization.network_flow_integrality

by Shuze Chen · Aug 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatorial-optimizationintegralitynetwork-flowsunimodularity

(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 B\mathbf{B}B, the matrix B−1\mathbf{B}^{-1}B−1 has integer entries.
  • (b) If the supplies bib_ibi​ are integer, then every basic solution has integer coordinates.
  • (c) If the cost coefficients cijc_{ij}cij​ are integer, then every dual basic solution has integer coordinates.

(Basis matrices are the nonsingular (n−1)×(n−1)(n-1)\times(n-1)(n−1)×(n−1) submatrices of A~\tilde{\mathbf{A}}A~ formed by the columns of the n−1n-1n−1 arcs of a tree, cf. Theorems 7.3-7.4; basic solutions satisfy fT=B−1b~\mathbf{f}_T=\mathbf{B}^{-1}\tilde{\mathbf{b}}fT​=B−1b~, dual basic solutions p′=cB′B−1\mathbf{p}'=\mathbf{c}_B'\mathbf{B}^{-1}p′=cB′​B−1, p. 289. Standing Assumption 7.1(a): ∑i∈Nbi=0\sum_{i\in\mathcal{N}}b_i=0∑i∈N​bi​=0.)

Preamble
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. -/
Formal statement
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
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 7.5, p. 289

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me