§3, p. 1779 — with all α_r ≥ 0 and every commodity chain of length Σ α_r a_rs ≥ 1, the arc-chain basis is optimal
ProvedFordFulkerson58.ArcChain.basis_optimal_of_chainLength_ge_oneConsider the arc-chain program (2)–(3) of a multi-commodity network. Let be a basis (columns of with invertible submatrix), its basic feasible solution, and its simplex multipliers (4). Interpret as the length of arc . Suppose that
- for every arc , and
- every commodity chain has length at least one: for all .
Then the basis is optimal: for every feasible solution of (3),
This is the optimality half of the pricing test of §3: once no chain is shorter than its objective coefficient , no column can enter and the simplex computation stops.
Formalization Note Optimality is stated against every feasible , with no supremum. The LP fact behind it is the simplex optimality criterion / weak duality, available as the referenced items MatousekLP.Simplex.optimality_criterion and MatousekLP.Duality.weak_duality.
import Mathlib import Definitions.Def_FordFulkerson58_ArcChain_Network import Definitions.Def_FordFulkerson58_ArcChain_LP import Definitions.Def_FordFulkerson58_ArcChain_Labeling
namespace FordFulkerson58.ArcChain
/-- §3, p. 1779: if the simplex multipliers of a feasible basis are non-negative and every commodity
chain has length `∑_r α_r a_rs ≥ 1` (the arc lengths being the multipliers), the basis is optimal: no
feasible flow has a larger total than the basic solution. -/
theorem basis_optimal_of_chainLength_ge_one {V E ι : Type*} [Fintype V] [DecidableEq V] [Fintype E] [DecidableEq E]
[Fintype ι] [DecidableEq ι] (N : Network V E ι)
(β : E → Col N ⊕ E) (hβ : IsUnit (basisMatrix N β).det)
(z : Col N ⊕ E → ℝ) (hz : IsBasicFeasibleSolution N β z)
(α : E → ℝ) (h4 : IsSimplexMultiplier N β α)
(hα : ∀ r, 0 ≤ α r) (hlen : ∀ s : Col N, (1 : ℝ) ≤ chainLength α s.1.2) :
∀ (x : Col N → ℝ) (y : E → ℝ), Feasible N x y → ∑ s, x s ≤ ∑ s, z (Sum.inl s) := by sorry
end FordFulkerson58.ArcChain
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.