Existence of integer optimal flows and integer dual optima
ProvedLinearOptimization.network_integer_optimum_exists(Bertsimas & Tsitsiklis, Corollary 7.2, p. 290) Consider an uncapacitated network flow problem, and assume that the optimal cost is finite.
- (a) If all supplies are integer, there exists an integer optimal flow vector.
- (b) If all cost coefficients are integer, there exists an integer optimal solution to the dual problem.
(Stated in §7.3 under standing Assumption 7.1: and the graph connected. The dual problem is the LP dual of the standard-form problem s.t. , .)
import Definitions.Def_LinearOptimization_NetworkFlowProblem import Definitions.Def_Polyhedron import Definitions.Def_LinearOptimization_DualLP open Matrix /-- **Bertsimas & Tsitsiklis, Corollary 7.2 (p. 290).** For the uncapacitated network flow problem `min c'f, Ãf = b̃, f ≥ 0` on a connected graph with `∑ᵢ bᵢ = 0` and finite optimal cost: integer supplies yield an integer optimal flow vector, and integer costs yield an integer optimal solution of the dual `max p'b̃, p'Ã ≤ c'`. -/
theorem LinearOptimization.network_integer_optimum_exists {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)
(hfin :
lpValue cost
(stdPolyhedron (truncatedIncidence arcs) (truncatedSupply bsupply)) ≠ ⊤ ∧
lpValue cost
(stdPolyhedron (truncatedIncidence arcs) (truncatedSupply bsupply)) ≠ ⊥) :
((∀ i, ∃ z : ℤ, bsupply i = (z : ℝ)) →
∃ f, IsLpOptimal cost
(stdPolyhedron (truncatedIncidence arcs) (truncatedSupply bsupply)) f ∧
∀ k, ∃ z : ℤ, f k = (z : ℝ)) ∧
((∀ k, ∃ z : ℤ, cost k = (z : ℝ)) →
∃ p, IsLpDualOptimal (truncatedSupply bsupply)
(dualFeasibleStd (truncatedIncidence arcs) cost) p ∧
∀ i, ∃ z : ℤ, p i = (z : ℝ)) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Fix naturals , a family of directed arcs on the nodes (arc is an ordered pair ), a supply vector , and a cost vector . Let be the incidence matrix with (so a self-loop gives a zero column), let be with its last row (node ) deleted, and the first entries of . Let — nonnegativity but no capacity bounds, and no balance constraint at node . Hypotheses: no arc is a self-loop; the network is connected, meaning any two nodes are related by the reflexive–transitive closure of "some arc joins and in either orientation"; ; and the extended-real value is neither (the value of an infimum over the empty set, i.e. ) nor . The conclusion is a conjunction: (a) if every equals an integer, then there exists with , for every (an exact minimizer), and every coordinate an integer; (b) if every cost equals an integer, then there exists lying in the dual feasible set with for every in that set (an exact maximizer of ), and every coordinate an integer.
Confirmed by the mission captain (proposal self-audit).