Theorem 1 — existence of minimum-cost flows and reduction to nonnegative arc costs
ProvedSendSplit.Existence.theorem1_existence_reductionLet be a graph whose arc costs are concave on with . The following are equivalent.
- (1°) There is a minimum-cost flow for some demand vector.
- (2°) The null circulation is a minimum-cost circulation.
- (3°) For every demand vector : if there is a flow for , there is a minimum-cost flow for that is extreme.
- (4°) Each simple circulation has nonnegative flow cost, .
- (5°) for every simple circuit of with arc set .
- (6°) For every set containing exactly one node of each sink strong component of and no other node, and every choice of the arc costs of the augmented graph ( inside strong components, arbitrary real numbers on the other arcs, including the appended arcs ), there is a minimum-cost chain to from each node of .
Moreover, let be a demand vector for which a flow exists, , and let , be as in 6° with
Then 1°–6° are also equivalent to
- (7°) there is with for every arc of and every flow for ;
and when they hold, the minimum chain costs in are real and satisfies 7°.
The theorem characterizes when a minimum-concave-cost uncapacitated flow problem has an optimum by a condition (4° or 5°) that does not involve the demands, gives a shortest-chain test for it (6°), and produces node potentials that turn the problem into an equivalent one with nonnegative arc costs (7°), which the send-and-split method then solves.
Formalization Note The equivalence of 1°–6° is List.TFAE. "Minimum-cost" always means attained: a feasible object whose cost is that of every feasible object. A minimum-cost chain must have real cost (see the AugmentedGraph definition). Chains are walks, not simple paths. The paper states the 7° part only with " is a demand vector"; this formalization adds the hypothesis that a flow for exists, which the paper assumes in the surrounding text ("if there is a flow"): without it 7° holds vacuously while 4° may fail (two nodes, arcs , , ). The inequality uses the real values of (EReal.toReal), which are exact because is shown real.
import Mathlib import Definitions.Def_SendSplit_Existence_Network import Definitions.Def_SendSplit_Existence_ReducedCost import Definitions.Def_SendSplit_Existence_AugmentedGraph
namespace SendSplit.Existence
theorem theorem1_existence_reduction {n : ℕ} (G : ArcGraph n) (c : Fin n → Fin n → ℝ → ℝ)
(hc : IsConcaveArcCost G c) :
List.TFAE
[ ∃ (r : Fin n → ℝ) (x : Fin n → Fin n → ℝ), IsMinCostFlow G c r x,
IsMinCostFlow G c (fun _ => 0) (fun _ _ => 0),
∀ r : Fin n → ℝ, (∃ x, IsFlow G r x) →
∃ x, IsMinCostFlow G c r x ∧ IsExtremeFlow G r x,
∀ y, IsSimpleCirculation G y → 0 ≤ flowCost G c y,
∀ C, IsSimpleCircuit G C → 0 ≤ ∑ p ∈ C, slopeAtInfty (c p.1 p.2),
∀ S, IsSinkSelection G S → ∀ (b : Fin n → Fin n → ℝ) (bν : Fin n → ℝ),
∀ u, HasMinCostChain G S (augCost G c b bν) u ] ∧
∀ (r : Fin n → ℝ) (S : Finset (Fin n)) (b : Fin n → Fin n → ℝ) (bν : Fin n → ℝ),
IsSinkSelection G S → (∃ x, IsFlow G r x) →
(∀ p ∈ G.A, ¬ SameComponent G p.1 p.2 →
b p.1 p.2 * (∑ i, max (r i) 0) ≤ c p.1 p.2 (∑ i, max (r i) 0)) →
(((∃ (r' : Fin n → ℝ) (x : Fin n → Fin n → ℝ), IsMinCostFlow G c r' x) ↔
∃ π : Fin n → ℝ, ∀ p ∈ G.A, ∀ x, IsFlow G r x →
0 ≤ reducedArcCost c π p.1 p.2 (x p.1 p.2)) ∧
((∃ (r' : Fin n → ℝ) (x : Fin n → Fin n → ℝ), IsMinCostFlow G c r' x) →
(∀ i, minChainCost G S (augCost G c b bν) i ≠ ⊥ ∧
minChainCost G S (augCost G c b bν) i ≠ ⊤) ∧
∀ p ∈ G.A, ∀ x, IsFlow G r x →
0 ≤ reducedArcCost c (fun i => (minChainCost G S (augCost G c b bν) i).toReal)
p.1 p.2 (x p.1 p.2))) := by sorry
end SendSplit.Existence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.