AFTD Auto-Formalizing Theoretical Domains

IsFeasibleMultiflow

def

A multicommodity flow function f : K → E → ℝ is feasible for capacities u : E → ℝ and demands d : K → ℝ on topology (G, H) if f is non-negative, total flow on each edge is at most capacity, and net outflow at each vertex equals source demand minus sink demand.

Statement

def IsFeasibleMultiflow {V E K : Type*} [Fintype E] [Fintype K] [DecidableEq V]
    (G : DirectedMultigraph V E) (H : DirectedMultigraph V K)
    (u : E → ℝ) (d : K → ℝ) (f : K → E → ℝ) : Prop
Defined in
arXiv:2611.12330 Section 2
Verified
13 Nov 2026
Axioms
none listed
Built on 1
  • DirectedMultigraphA directed multigraph parameterized by vertex type V and edge type E, with source and target maps src : E → V and tgt : E → V.
Used by 2
  • HasFeasibleMultiflowAn instance (G, H, u, d) has a feasible multiflow if there exists some flow function f : K → E → ℝ satisfying IsFeasibleMultiflow G H u d f.
  • HasIntegralMultiflowAn instance (G, H, u, d) has an integral multiflow if there exists a feasible multiflow f : K → E → ℝ such that every f i e is a natural…

Read back from the Lean

Given types V, E, and K with E and K finite and V having decidable equality, directed multigraphs G on vertices V and edges E and H on vertices V and demand edges K (each specified by src and tgt maps to V), an edge capacity function u : E → ℝ, a demand function d : K → ℝ, and a flow assignment f : K → E → ℝ, IsFeasibleMultiflow G H u d f is the proposition that: 1. (Nonnegativity) For every commodity i : K and edge e : E, f i e ≥ 0. 2. (Capacity constraint) For every edge e : E, the sum over all commodities i : K of f i e is at most u e. 3. (Flow conservation / demand satisfaction) For every commodity i : K and vertex v : V, the net outflow of commodity i at v—defined as (the sum over all e : E with G.src e = v of f i e) minus (the sum over all e : E with G.tgt e = v of f i e)—equals (if H.src i = v then d i else 0) - (if H.tgt i = v then d i else 0).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Feasibility of a multiflow: nonnegativity, capacity bounds, and vertex conservation equations. -/
def IsFeasibleMultiflow {V E K : Type*} [Fintype E] [Fintype K] [DecidableEq V]
    (G : DirectedMultigraph V E) (H : DirectedMultigraph V K)
    (u : E → ℝ) (d : K → ℝ) (f : K → E → ℝ) : Prop :=
  (∀ i e, 0 ≤ f i e) ∧
  (∀ e, (∑ i : K, f i e) ≤ u e) ∧
  (∀ i v, (∑ e : E, if G.src e = v then f i e else 0) - (∑ e : E, if G.tgt e = v then f i e else 0) =
    (if H.src i = v then d i else 0) - (if H.tgt i = v then d i else 0))
See it in the graphDiscuss this resultChallenge it