Infinite networks: Minimal cost flows

Benno Fuchssteiner and Karsten Morisse University of Paderborn

Abstract

We are concerned with the minimal cost flow problem in infinite networks. The generalisation to infinite networks is made in order to provide tools for the study of the dynamics of such networks. By disintegration methods we obtain that the minimal transportation costs are the supremum of the differences between consumption cost and transportation profit taken over all local price systems. Thus by our method results which for finite networks usually are obtained by the strong duality theorem can be generalized to infinite networks. Keywords: Minimal cost flow problem, infinite networks, disintegration theory.

1 The main result

The classical minimal cost flow problem (MCFP) is to determine a minimum cost shipment of a commodity through a network which satisfies demand at certain nodes by use of available supplies at other nodes. To be precise, let there be given a (finite) set Ω of consumers with consumption at i ∈ Ω denoted by μ_{i} and where production is meant to be negative consumption. There are pipelines E ⊆ Ω × Ω between consumers (i.e. arcs in the corresponding graph) where τ_{k,i} measures the capacity of the arc running from k to i and γ_{k,i} is the associated cost for the transport (per unit) from k to i. An admissible flow ν is a mapping from E to IR_{+} with 0 ≤ ν_{k,i} ≤ τ_{k,i} ∀i, k ∈ Ω such that μ_{i} ≤ ∑_{k∈Ω}(ν_{k,i} − ν_{i,k}) ∀i ∈ Ω. The MCFP is to find an admissible flow with minimal cost, i.e. to minimize transportation cost T C

minimize_{|ν=admissible} T C(γ, ν) := ∑_{(k,i)∈E} ν_{k,i}γ_{k,i}.

For linear programming problems the concept of duality attributed to J. von Neumann (see [4] page 123, or [11] page 12) is of great importance, it states: If solutions to the primal and dual system exist, then the value z of the objective function corresponding to any admissible solution of the primal problem is greater than or equal to the value ω of the objective function corresponding to any admissible solution of the dual problem. Moreover, optimal admissible solutions exist for both problems and min z = max ω (see [12] for its first proof). Dual to the MCFP is the following objective function ω(π) = ∑_{i∈Ω} μ_{i}π_{i} − ∑_{(i,j)∈E} τ_{i,j} max(0, π_{i} − π_{j} − γ_{i,j}), where the π_{i} are the dual variables. By application of the strong duality theorem we have the following: If there exists an admissible flow for the MCFP then min_{ν} T C(γ, ν) = max_{π} ω(π).

The dual problem has an interesting economic interpretation. Consider the dual variables as prices, i.e. π_{i} is the price to pay for the commodity at the site of consumer i. Then rephrasing the min-max condition one sees that once a suitable price system is found then the minimal cost flow is obtained if at each node that action is taken which yields the greatest profit. Thus, if price differences between beginning and end point at some arc are exceeding transportation cost then the flow has to attain full capacity, and no flow takes place if transportation cost is higher than this price difference. And at those arcs where the price difference equals the shipment cost there the flow has to be chosen such that there is a balance between consumption-production and transportation at the adjacent points.

Several algorithms based on this dual cost improvement approach can be found in the literature, e.g. the primal-dual algorithm [6], out-of-kilter algorithm [10] and the relaxation method ([1] or [2]). Even though there are algorithms with a superior theoretical complexity, the latter method is one of the fastest algorithms in practice (see [3], [5], or [13]).

We are now going to generalize this situation to infinite consumer sets. This generalization is necessary, if one is — for example — interested in the dynamical behaviour of such a system because then consumers and pipes at different times are considered as different nodes. The same generalisation is necessary if one studies how selforganisation over time may lead to an equilibrium.

For the infinite system it is convenient to substitute the quantities μ, τ, γ and ν by suitable measures and functions on Ω × Ω and Ω, respectively. Furthermore, all local arguments are replaced by almost-everywhere considerations. So let from now on (Ω, Σ) be a measurable space, given by a suitable σ-algebra Σ on the consumer set Ω. For finite Ω the foregoing situation is recovered by defining τ_{k,i} and μ_{i} as the applications of the measures τ, μ to the corresponding singletons, i.e by τ({(k, i)}) and μ({i}), respectively.

Given a signed measure μ : Ω → IR (consumption), a σ-finite positive measure τ : Ω × Ω → IR_{+} (capacity) and some L^{1}(τ)-function γ : Ω × Ω → IR_{+} (cost) with γ(ω, ω) = 0 for almost all ω. Some L^{∞}(τ)-function ν : Ω × Ω → IR with ν ≤ 1 and ∫_{B×A} νdτ ≥ 0 for B ∩ A = ∅ is said to define an admissible flow, if it satisfies demand, without exceeding supply, i.e. if μ(A) ≤ ∫_{(Ω\A)×A} νdτ − ∫_{A×(Ω\A)} νdτ. Because of ν ≤ 1 the capacity bound is automatically observed.

The general theory yields that there is an admissible flow if and only if μ(A) ≤ τ(A × (Ω \ A)) for all A ∈ Σ (see [9] page 57). The cost of a flow ν is defined to be Γ(γ, ν) := ∫_{Ω×Ω} νγdτ. The minimal cost flow problem then is to find an admissible flow with minimal cost.

In order to solve this we introduce non negative L^{1}(μ)-functions f on Ω as local price systems, where f(ω) denotes the price of the commodity at the site of consumer ω. The consumption cost, under the price system f, then is C(f) = ∫_{Ω} fdμ. We define ρ̂_{f} : Ω × Ω → IR_{+} by ρ̂_{f}(ω_{1}, ω_{2}) = max(0, f(ω_{1}) − f(ω_{2}) − γ(ω_{1}, ω_{2})), and ρ(f, γ) := ∫_{Ω×Ω} ρ̂_{f}dτ as the optimal transportation profit under the given price system f with respect to the cost function γ.

Since the actual flow does not enter this definition, at the moment it is not at all clear if such a most profitable flow can be realized by admissible flows. This optimal profit only is possible if there is an admissible flow such that it attains the value of full capacity whenever transport is profitable with respect to transportation cost and local prices. The following result shows that a most profitable minimal cost flow exists and that it is determined by a suitable price system: Minimal transportation cost theorem: Let there be an admissible flow, then there also is an admissible flow ν such that its transportation cost under γ is the supremum (over all local price systems) of the difference between consumption cost and optimal transportation profit, i.e.

Γ(γ, ν) = sup{C(f) − ρ(f, γ) | f local price system}  (1.1)

Furthermore, ν necessarily is a minimal cost flow. That ν has minimal cost is a direct consequence of the simple fact that for any admissible flow the transportation cost must be greater than or equal to the right hand side of (1.1).

2 Principal tools

First, we gather some of the tools needed to prove the main result (see [8], [7] or for a survey [9]). We consider \overline{IR} := IR ∪ \{−∞\} with the usual extensions of the algebraic operations. Moreover, we consider a cone F with compatible preorder ≺ (all cones are assumed to be convex, and compatible means that inequalities can be treated in the usual way). As usual, we call a functional π : F → \overline{IR} monotone if f_{1} ≺ f_{2} implies π(f_{1}) ≤ π(f_{2}), such a functional is said to be homogeneous, if π(λf) = λπ(f) for all f ∈ F and λ ∈ IR_{+}. A functional π is said to be sublinear, if it is homogeneous and subadditive, i.e. π(f_{1} + f_{2}) ≤ π(f_{1}) + π(f_{2}) for all f_{1}, f_{2} ∈ F. If for all f_{1}, f_{2} ∈ F we have π(f_{1} + f_{2}) ≥ π(f_{1}) + π(f_{2}) instead then π is called superadditive, and superlinear if it is in addition homogeneous. A functional is called linear, if it is sub- and superlinear. For a subcone G of F and for superlinear μ on G and monotone and sublinear π on F we define

Lin(μ, π) := \{ν | ν : F → \overline{IR} is monotone and linear with μ ≤ ν on G and ν ≤ π on F\}.

It is well known [9] that Lin(μ, π) ≠ ∅ iff μ ≤ π. This is a consequence of the following extension (DET) of the classical Hahn-Banach Theorem: Dominating Extension Theorem (see [9]): Let G be a subcone of the preordered cone (F, ≺). Consider a superlinear functional μ̂ on G and a monotone sublinear π on F with μ̂(g) ≤ π(g) for all g ∈ G. Then there is a monotone linear μ on F with μ̂ ≤ μ on G and μ ≤ π on F. Fix a subcone G of F, some superlinear μ on G and a monotone and sublinear π on F with μ ≤ π on G. For f ∈ F we define ω(f) := sup{μ(g) − π(h) | g ≺ f + h, g ∈ G, h ∈ F} and obtain:

i) ω(f) ≤ inf{ν(f) | ν ∈ Lin(μ, π)} for all f ∈ F, ii) μ ≤ ω on G and ω ≤ π on F, iii) ω is superlinear.

Proof: Assertion i) follows from the fact that for ν ∈ Lin(μ, π) and for g ∈ G and f, h ∈ F with g ≺ f + h we have: μ(g) ≤ ν(g) ≤ ν(f + h) = ν(f) + ν(h) ≤ ν(f) + π(h). For ii) we take in the right side of the definition of ω and put h = 0 then μ ≤ ω is evident and ω ≤ π is a consequence of i). Finally, a simple computation yields iii). This results in another characterization of ω.

Lemma 1 Fix f ∈ F with ω(f) ≠ −∞, then

ω(f) = inf{ν(f) | ν ∈ Lin(μ, π)} = sup{μ(g) − π(h) | g ≺ f + h, g ∈ G, h ∈ F}.  (2.2)

Proof: We define ρ(h) := inf{λω(f) + π(g) | h ≺ λf + g, g ∈ F, λ ≥ 0} for h ∈ F. Obviously, ρ ≤ π and ρ is monotone and sublinear. By definition of ω we have λω(f) + π(g) ≥ μ(h) whenever h ≺ λf +g, therefore μ ≤ ρ on G. Hence, we can apply the DET to obtain a monotone linear functional ν with μ ≤ ν on G and ν ≤ ρ on F. Of course, this is an element of Lin(μ, π) and furthermore we have

ν(f) ≤ ρ(f) = inf{λω(f) + π(g) | h ≺ λf + g, λ ≥ 0} ≤ ω(f).

Together with i), i.e. ω(f) ≤ ν(f), we therefore have shown (2.2).

3 Determination of the most profitable flow

We take measures μ, τ as before and assume that μ(A) ≤ τ(A × Ω \ A) for all A ∈ Σ, which is equivalent to the existence of an admissible flow. To prove the main result, we establish a suitable framework to apply the tools of section 2. Let F be the space of all L^{1}(dτ̃)-functions on Ω, where τ̃(A) := τ(Ω × A). Denote by F_{+} its positive cone. Observe that with respect to evaluation of suitable positive measures F_{+} may be approximated by the elements of the positive linear hull of the characteristic functions χ_{A}, A ∈ Σ, i.e. the positive simple measurable functions. An element of F_{+} is said to be a local price system. For real functions on Ω we define a collection {≺_{(ω_{1},ω_{2})} | ω_{1}, ω_{2} ∈ Ω} of order structures by

f ≺_{(ω_{1},ω_{2})} g ⟺ f(ω_{1}) ≥ g(ω_{1}) and f(ω_{2}) ≤ g(ω_{2}),

and a functional p_{f} : Ω × Ω → IR_{+} by p_{f}(ω_{1}, ω_{2}) := max(0, f(ω_{2}) − f(ω_{1})). The map f → p_{f} is sublinear and ≺_{(ω_{1},ω_{2})}-monotone. The consumption cost ∫_{Ω} fdμ under the price system f is considered as a linear functional on F_{+}. We consider the space Φ := {φ : Ω × Ω → F} and K(Φ) its subcone of F_{+}-valued constant functions. For convenience, for the elements of K(Φ) we write φ_{f} when φ_{f}(ω_{1}, ω_{2}) = f for almost all (ω_{1}, ω_{2}) ∈ Ω × Ω. We define a preorder ≺_{Φ} on Φ by

φ_{1} ≺_{Φ} φ_{2} ⟺ φ_{1}(ω_{1}, ω_{2}) ≺_{(ω_{1},ω_{2})} φ_{2}(ω_{1}, ω_{2}) for almost all (ω_{1}, ω_{2}) ∈ Ω × Ω.

Moreover, we define a linear functional μ̂ on K(Φ) by μ̂(φ_{f}) := ∫_{Ω} fdμ and a sublinear ≺_{Φ}- monotone functional π̂ by π̂(φ) := ∫_{Ω×Ω} p_{φ(ω_{1},ω_{2})}(ω_{1}, ω_{2})dτ(ω_{1}, ω_{2}). A simple computation shows μ̂(φ_{f}) ≤ π̂(φ_{f}) ∀φ_{f} ∈ K(Φ) (when f is a positive simple function see [9] page 50, by approximation this then holds for all elements of K(Φ)). Hence, μ̂ ≤ π̂ on K(Φ). For cost measure γ and for A, B ∈ Σ we define maps γ̃, α_{B×A} : Ω×Ω → F, thus elements of Φ, by setting for almost all ω ∈ Ω and (ω_{1}, ω_{2}) ∈ Ω × Ω

α_{B×A}(ω_{1}, ω_{2})(ω) := χ_{B}(ω_{1})χ_{A}(ω)  (3.3)
γ̃(ω_{1}, ω_{2})(ω) := γ(ω_{1}, ω)  (3.4)

By use of the DET we fix some monotone ν̂ ∈ Lin(μ̂, π̂) such that ν̂(γ̃) is minimal and we define a flow ν by taking, with respect to τ, the density of the measure B×A → ν̂(α_{B×A}), i.e. ν̂(α_{B×A}) = ∫_{B×A} νdτ. For A∩B = ∅ we have 0≺_{Φ}α_{B×A} and therefore ∫_{B×A} νdτ ≥ 0. Because of ν̂(α_{B×A}) ≤ π̂(α_{B×A}) = τ((B \ A) × A) we have ν ≤ 1 and ∫_{A×Ω} νdτ ≤ τ((A \ Ω) × Ω) = 0. So, because of ∫_{A×Ω} νdτ ≤ 0 we find μ(A) = μ̂(α_{Ω×A}) ≤ ν̂(α_{Ω×A}) = ∫_{Ω×A} νdτ ≤ ∫_{Ω×A} νdτ − ∫_{A×Ω} νdτ. Hence, ν is admissible. The transportation cost of ν is Γ(γ, ν) = ∫_{Ω×Ω} νγdτ = ν̂(γ̃); this identity is easily seen for the case when γ = χ_{B×A} is a characteristic function and then extended to the general case by linearity. Hence, to determine the flow cost we have to compute the minimal value ν̂(γ̃). This value can be evaluated with lemma 1 as sup{μ̂(φ_{f}) − π̂(φ) | φ_{f} ≺_{Φ} γ̃ + φ, f ∈ F, φ ∈ Φ}. This expression becomes

ν̂(γ̃) = sup{μ̂(φ_{f}) − π̂(φ) | φ_{f} ≺_{Φ} γ̃ + φ} = sup{μ̂(φ_{f}) − π̂(φ_{f} − γ̃) | φ_{f} ∈ K(Φ)}

This last identity came from the monotonicity of π̂ by use of the fact that the minimal φ with φ_{f} ≺_{Φ} γ̃ + φ is φ_{f} − γ̃. Now inserting μ̂ and π̂ and observing that γ(ω, ω) = 0 we find ν̂(γ̃) to be sup{∫_{Ω} fdμ − ∫_{Ω×Ω} max(0, f(ω_{1}) − f(ω_{2}) − γ(ω_{1}, ω_{2}))dτ | f ∈ F_{+}}, which shows that ν is a most profitable flow.

References

[1] D.P. Bertsekas. A Unified Framework for Primal-Dual Methods in Minimum Cost Network Flow Problems. Mathematical Programming, 32:125–145, 1985.

[2] D.P. Bertsekas. Linear Network Optimization: Algorithms and Codes. The MIT Press, Cambridge (Massachusetts)-London, 1991.

[3] D.P. Bertsekas and P. Tseng. The Relax Codes for Linear Minimum Cost Network Flow Problems. Annals of Operations Research, 13:125–190, 1988.

[4] G.B. Dantzig. Linear Programming and Extensions. Princeton University Press, Princeton, New Jersey, 1963.

[5] D.P.Bertsekas and P. Tseng. RELAX-IV: A Faster Version of the RELAX Code for Solving Minimum Cost Flow Problems. Technical report, Preprint, November 1994.

[6] L.R. Ford Jr. and D.R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, New Jersey, 1962.

[7] B. Fuchssteiner. An Abstract Disintegration Theorem. Pacific Journal of Mathematics, 94(2):303–309, 1981.

[8] B. Fuchssteiner. Disintegration Methods in Mathematical Economics. In O. Moeschlin and D. Pallaschke, editors, Game Theory and Mathematical Economics, pages 193–204, Amsterdam-New York, 1981. Elsevier Science Publishers B.V. (North-Holland).

[9] B. Fuchssteiner and W. Lusky. Convex Cones, volume 56 of Mathematics Studies. Elsevier Science Publishers B.V. (North-Holland), Amsterdam-New York-Oxford, Amsterdam-New York-Oxford, 1981.

[10] D.R. Fulkerson. An Out-of-Kilter Method for Minimal-Cost Flow Problems. Journal of the Society for Industrial and Applied Mathematics, 9(1):18–27, March 1961.

[11] D. Gale. The Theory of Linear Economic Models. McGraw-Hill Book Company, New York-Toronto-London, 1960.

[12] D. Gale, H.W. Kuhn, and A.W. Tucker. Linear Programming and the Theory of Games. In T.C. Koopmans, editor, Activity Analysis of Production and Allocation, 1951.

[13] M.D. Grigoriadis. An efficient implementation of the network simplex algorithm. Mathematical Programming Studies, 26:83–111, March 1986.