Theorem 14.2 — Integrality Theorem
ProvedVanderbeiLP.Networks.integrality_theoremLet be a connected network with supplies , , and suppose the data are integers: every . Fix a root node . Then every basic feasible solution of the network flow problem (14.1) is integral:
In particular every basic optimal solution assigns integer flow to every arc, whatever the costs .
The theorem makes network flow problems with integer data integer programs that the simplex method solves exactly; it is the tool behind König's Theorem 14.3.
Formalization Note "Integer data" means integral supplies and demands only (p. 215); the costs play no role and are omitted. A basic optimal solution is a basic feasible solution, so the "in particular" clause of the book is contained in the statement. The standing assumptions (p. 200) and connectedness (p. 202) are hypotheses.
import Mathlib import Definitions.Def_VanderbeiLP_Networks_Network
namespace VanderbeiLP.Networks
/-- **Theorem 14.2, Integrality Theorem** (Vanderbei, *Linear Programming*, 4th ed., p. 216).
For a network flow problem (14.1) on a connected network with integer supplies/demands
(`∑ b_i = 0`), every basic feasible solution assigns integer flow to every arc. (Every basic
optimal solution is in particular a basic feasible solution.) -/
theorem integrality_theorem {N : Type*} [Fintype N] [DecidableEq N]
(A : Finset (N × N)) (hA : IsNetwork A) (hconn : IsConnectedNetwork A)
(b : N → ℝ) (hsum : ∑ i, b i = 0) (hb : ∀ i, ∃ z : ℤ, b i = z)
(r : N) (x : N × N → ℝ) (hx : IsBasicFeasibleFlow A b r x) :
∀ a ∈ A, ∃ z : ℤ, x a = z := by sorry
end VanderbeiLP.Networks
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.