Basic solutions are exactly tree solutions
ProvedLinearOptimization.network_basic_iff_tree(Bertsimas & Tsitsiklis, Theorem 7.4, p. 283) A flow vector is a basic solution if and only if it is a tree solution.
(Setting: the uncapacitated network flow problem in standard form with constraints , , under standing Assumption 7.1: and connected. 'Basic solution' is in the sense of Bertsimas & Tsitsiklis, Definition 2.9 / Mission I's BasicSolution; consequently a feasible tree solution is a basic feasible solution, p. 283.)
import Definitions.Def_LinearOptimization_TreeSolution import Definitions.Def_BasicSolution open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 7.4 (p. 283).** For the uncapacitated network flow problem `Ãf = b̃`, `f ≥ 0` on a connected graph with `∑ᵢ bᵢ = 0`, a flow vector is a basic solution (in the Definition 2.9 sense, for the truncated standard-form constraint system) if and only if it is a tree solution. -/
theorem LinearOptimization.network_basic_iff_tree {n m : ℕ}
(arcs : Fin m → Fin (n + 1) × Fin (n + 1)) (bsupply : Fin (n + 1) → ℝ)
(hloop : HasNoSelfLoops arcs) (hconn : IsConnectedNetwork arcs)
(hsum : ∑ i, bsupply i = 0) (f : Fin m → ℝ) :
IsBasicSolution
(stdFormSystem (truncatedIncidence arcs) (truncatedSupply bsupply)) f ↔
IsTreeSolution arcs bsupply f := 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 indexed by (ordered tail–head pairs); hypotheses: no self-loops, the network is connected (reflexive–transitive closure of either-direction adjacency relates every pair of nodes), and for the supply vector . Let be the truncated incidence matrix (; entry where node tail, where node head, last node's row deleted) and the truncated supply. The theorem asserts, for every , the equivalence of: (1) is a basic solution of the standard-form constraint system of — this system has constraints on vectors in : the equality constraints and the inequality constraints ; “basic solution” means every equality constraint holds at , and there exists a set of of these constraints, each active at (equality constraint: ; sign constraint: ), whose coefficient vectors ( resp. the standard basis vector ) form a linearly independent family in ; iff (2) is a tree solution: there exists a finite arc set with that connects all nodes through its arcs, such that for and . Note that neither side imposes : side (1) is “basic”, not “basic feasible”, and side (2) carries no sign condition.
Confirmed by the mission captain (proposal self-audit).