Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3, pp. 1779–1780 — with α ≥ 0, the labeling process terminates; sink labels ≥ 1 ⇒ the basis is optimal; a sink label < 1 ⇒ an entering chain

Proved
FordFulkerson58.ArcChain.shortest_chain_pricing_test

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

column-generationlinear-programmingmulticommodity-flowp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1shortest-chainsimplex-method

Consider the arc-chain program (2)–(3) of a multi-commodity network with arcs A1,…,AmA_1,\dots,A_mA1​,…,Am​. Let BBB be a basis (columns s1,…,sms_1,\dots,s_ms1​,…,sm​ of [A∣I][A\mid I][A∣I] with invertible submatrix), zzz its basic feasible solution, and α1,…,αm\alpha_1,\dots,\alpha_mα1​,…,αm​ its simplex multipliers, i.e. the solution of (4). Assume all αr≥0\alpha_r \ge 0αr​≥0, and run the labeling process of §3 for each commodity kkk with arc lengths αr\alpha_rαr​, starting from πi=0\pi_i = 0πi​=0 on the sources SkS_kSk​ and πi=∞\pi_i = \inftyπi​=∞ elsewhere. Then:

  1. (termination) for every commodity, every run of the labeling process is finite;
  2. (optimality) if, for every commodity kkk, the final labels π(k)\pi^{(k)}π(k) satisfy πt(k)≥1\pi^{(k)}_t \ge 1πt(k)​≥1 at every sink t∈Tkt \in T_kt∈Tk​, then the basis is optimal: every feasible solution of (3) has
∑s=1nxs≤∑s=1nzs;\sum_{s=1}^{n} x_s \le \sum_{s=1}^{n} z_s;s=1∑n​xs​≤s=1∑n​zs​;
  1. (entering chain) if, for some commodity kkk, the final labels satisfy πt<1\pi_t < 1πt​<1 at some sink t∈Tkt \in T_kt∈Tk​, then there is a commodity chain CsC_sCs​ of kkk from SkS_kSk​ to ttt whose length ∑rαrars\sum_r \alpha_r a_{rs}∑r​αr​ars​ equals πt\pi_tπt​, whose column is not in the basis, and whose reduced cost is positive:
1−∑r=1mαrars>0,1 - \sum_{r=1}^{m} \alpha_r a_{rs} > 0,1−r=1∑m​αr​ars​>0,

so the column of AAA corresponding to this chain may be introduced into the basis.

This is the paper's main proposal: the pricing step of the simplex method on the arc-chain program, which would otherwise require the whole incidence matrix AAA, is carried out by one shortest chain computation per commodity.

Formalization Note "Final labels" means a labeling reachable from the initial labels by steps of the process and admitting no further step; part 1 shows such labelings exist, so parts 2 and 3 are not vacuous. Part 3 claims a positive reduced cost and non-basicness only; the page claims no strict increase of (2), which can fail under degeneracy. Labels are in WithTop ℝ; a sink with label ∞\infty∞ (no chain) counts as ≥1\ge 1≥1.

Preamble
import Mathlib
import Definitions.Def_FordFulkerson58_ArcChain_Network
import Definitions.Def_FordFulkerson58_ArcChain_LP
import Definitions.Def_FordFulkerson58_ArcChain_Labeling
Formal statement
namespace FordFulkerson58.ArcChain

/-- §3, pp. 1779–1780, the shortest-chain pricing test. Let `β` be a feasible basis of the arc-chain
program (2)–(3) with basic solution `z` and simplex multipliers `α` (4), all `α_r ≥ 0`, and use the
`α_r` as arc lengths. Then
(a) for every commodity, the labeling process from the commodity's sources terminates;
(b) if for every commodity the final labels at all its sinks are at least `1`, the basis is optimal;
(c) if for some commodity the final label of a sink `t` is below `1`, there is a chain from the
commodity's sources to `t` of length equal to that label, whose column is not basic and has positive
reduced cost `1 − ∑_r α_r a_rs`, so it may be introduced into the basis. -/
theorem shortest_chain_pricing_test {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) :
    (∀ k : ι, ¬ ∃ f : ℕ → V → WithTop ℝ,
        f 0 = initLabel (N.src k) ∧ ∀ i, RelaxStep N α (f i) (f (i + 1))) ∧
    (∀ lab : ι → V → WithTop ℝ,
        (∀ k, Relation.ReflTransGen (RelaxStep N α) (initLabel (N.src k)) (lab k) ∧
          IsTerminal N α (lab k)) →
        (∀ k, ∀ t ∈ N.snk k, (1 : WithTop ℝ) ≤ lab k t) →
        ∀ (x : Col N → ℝ) (y : E → ℝ), Feasible N x y → ∑ s, x s ≤ ∑ s, z (Sum.inl s)) ∧
    (∀ (k : ι) (lab : V → WithTop ℝ),
        Relation.ReflTransGen (RelaxStep N α) (initLabel (N.src k)) lab → IsTerminal N α lab →
        ∀ t ∈ N.snk k, lab t < 1 →
        ∃ (C : Finset E) (h : IsCommodityChain N k C), IsChainFrom N (N.src k) t C ∧
          ((chainLength α C : ℝ) : WithTop ℝ) = lab t ∧
          0 < reducedCost N α (Sum.inl ⟨(k, C), h⟩) ∧
          (Sum.inl ⟨(k, C), h⟩ : Col N ⊕ E) ∉ Set.range β) := by sorry

end FordFulkerson58.ArcChain
Source
Ford and Fulkerson, A suggested computation for maximal multi-commodity network flows, Management Sci. 50(12S) (2004), pp. 1779–1780, §3 (the pricing test on p. 1779 and the labeling process on p. 1780)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

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