A multi-material transport problem and its convex relaxation via rectifiable $G$-currents
Andrea Marchese Annalisa Massaccesi Riccardo Tione
math.AP math.OC 49Q10, 49Q15, 49Q20, 53C38, 90B06, 90B10





















 






 





Lip-schitz sub-space


backgrounds
decorations.pathmorphing,backgrounds,fit,calc,through
arrows
shapes,decorations,shadows

fadings
patterns
mindmap
decorations.text
decorations.shapes






fillbetween
patterns


























= 15.5 cm
= 24.45 cm
= -0.3 cm
= .1 cm

= 20 cm










1000









plain 
theoremTheorem[section]
lem[theorem]Lemma
prop[theorem]Proposition
thm[theorem]Theorem
cor[theorem]Corollary
question[subsection]Question
remark[theorem]Remark
example[theorem]Example

defn[theorem]Definition
equationsection

mytheorem





.
 
#2. #1 #3

myremark





.
 
#2. #1 #3

myparagraph





.
 
#2. #1#3




























secnumfont


§ STARTSECTIONSECTION1
@1.5PLUS .2.7




@headings@empty
 evenhead
  runhead
  @warning
  
 oddhead
  runhead
  @warning
  
mkboth







































	




	
	



	


	




	





	
	
	
	







	




	


	
	
	
addtoresetfootnotesection


itemizeb
=2pt
	
	
	


















A. Mar.: Dipartimento di Matematica “F. Casorati”, Università degli Studi di Pavia
andrea.marchese@unipv.it


A. Mas.: Department of Computer Science, University of Verona
annalisa.massaccesi@univr.it


R.T.: Mathematik Institut der Universität Zürich
riccardo.tione@math.uzh.ch





A multi-material transport problem and its convex relaxation via rectifiable G-currents
    Riccardo Tione
    December 30, 2023
=======================================================================================






	
	
Abstract.
In this paper we study a variant of the branched transportation problem, that we call multi-material transport problem. This is a transportation problem, where distinct commodities are transported simultaneously along a network. The cost of the transportation depends on the network used to move the masses, as it is common in models studied in branched transportation. The main novelty is that in our model the cost per unit length of the network does not depend only on the total flow, but on the actual quantity of each commodity. This allows to take into account different interactions between the transported goods. We propose an Eulerian formulation of the discrete problem, describing the flow of each commodity through every point of the network. We prove existence of solutions under minimal assumptions on the cost. Moreover, we prove that, under mild additional assumptions, the problem can be rephrased as a mass minimization problem in a class of rectifiable currents with coefficients in a group, allowing to introduce a notion of calibration. The latter result is new even in the well studied framework of the “single-material” branched transportation.
Keywords: Branched transportation, rectifiable currents, calibrations, multi-material transport problem. 
MSC (2010): 49Q10, 49Q15, 49Q20, 53C38, 90B06, 90B10.







§ INTRODUCTION


In this paper we study the multi-material transport problem (MMTP). Informally, given two arrays

    μ^-=(μ^-_1,…,μ^-_m),  μ^+=(μ^+_1,…,μ^+_m)
 
of discrete positive measures on ^d, we study transportation networks between μ^- and μ^+ of the form T=(T_1,…,T_m), where each T_i is a vector valued measure on ^d (with values also in ^d) having distributional divergence 

    div(T_i)=μ^-_i-μ^+_i    ∀ i=1,…,m .

More precisely, we will consider only transportation networks with a certain structure, namely we require that there exists a 1-rectifiable set E⊂^d (endowed with a unit vectorfield τ, orienting the approximate tangent of E) and for every i=1,…,m a subset E_i⊂ E and a multiplicity θ_i∈ such that 

    T_i:=θ_iτ^1 E_i,

where the latter means that, for every continuous and compactly supported vectorfield v on ^d, we have

    ⟨ T_i,v⟩=∫_E_i⟨τ(x); v(x)⟩θ_i(x)  d^1(x) .




Then we associate to T: 


  ∘ the multiplicity θ=(θ_1,…,θ_m), which is a function on E with values in ^m, 

  ∘ the vector valued measure on ^d (with values in ^d× m)

    T:=(τ⊗θ)^1 E,
 

  ∘ and the energy

    (T):=∫_E (θ) d^1,

where :^m→[0,+∞) is a cost function. 

The MMTP consists in the minimization of the energy (<ref>) under the constraint (<ref>).


We briefly step back for a heuristic introduction to the problem. In optimal transport problems one can focus on specific (concave) costs, which favor the aggregation of moved particles and generate optimal structures with branching. The branched transport problem is named after this peculiar phenomenon. A great interest has been devoted to branched transportation problems in the last years, providing several results concerning existence of solutions  <cit.>, regularity and stability <cit.> and strategies to compute minimizers or to prove minimality of concrete configurations <cit.>. 

Nonetheless, to our knowledge only problems involving the transport of one (homogeneous) material have been studied and modeled as variational problems. These models do not apply in planning a network for the transportation of different goods, whose mutual interactions require a formulation which involves several variables. The easiest examples of natural multi-material transport problem concern mixed-use roads (where vehicles of different size and pedestrians are allowed to circulate) and the transport through vehicles for goods and passengers. 

Another notable example is given by the power line communications technology (PLC, see <cit.>), which uses the electric power distribution network for data transmission. PLC has been introduced in the United States of America more than a century ago and used for the communications on moving trains or, more generally, for maintenance operations of the electric power network. Recently, a special type of PLC, the broadband over power lines (BPL) is being studied and improved for high-speed data transmission, being particularly convenient for isolated areas. Electric power and data signals are impossible to be treated as a homogeneous “material” for several reasons the main one being the fact that the electricity and the Internet supply are subject to different costs, depending on the users' concentration and demands.

Similar problems, usually grouped under the name of multi-commodity flow problems, were studied (see e.g. <cit.>) as minimization problems on graphs, often considering also constraints on the capacity of the network. Up to now, the aim of the research in this area was mainly devoted to study the complexity of the problem and to improve the efficiency of algorithms for numerical solutions.

The main results of the present paper are the existence of solutions to the minimization of the energy (<ref>) under the constraint (<ref>), with minimal assumptions on the cost  (Theorem <ref>) and, under mild additional assumptions, the equivalence between the MMTP and a mass minimization problem in a class of rectifiable currents with coefficients in a group (Theorem <ref>). The equivalence between the two problems allows us to introduce the notion of calibrations in this context. This was initiated in previous works (<cit.>) for “single-material” branched transportation problems and for very special choices of the cost functionals (i.e., the Steiner cost and the Gilbert-Steiner α-mass, respectively) and the benefit of introducing calibrations in such contexts is witnessed e.g. by <cit.>. Under our general assumptions on the cost, the equivalence result is new even in the case of “single-material” transportation problems. 
   


§ ACKNOWLEDGMENTS


The first named author is supported by the ERC-grant 306247 Regularity of area minimizing
currents. This project has received funding from the European Union's Horizon 2020 research and innovation programme under the grant agreement No 752018 (CuMiN). 
We warmly thank D. Vittone for valuable discussions and the anonymous referees for suggesting several improvements.






§ NOTATION AND PRELIMINARIES

Consider a norm · on ^n and its dual norm ·^*. The Euclidean norm is instead denoted by |·| and we will always denote an orthonormal basis of (^n, |·|) by { e_1,…, e_n}. The scalar product between vectors v and w of ^n is denoted ⟨ v;w⟩. Our aim is to define (1-dimensional) currents in ^d with coefficients in (^n,·).  Through the paper we will always use d for the dimension of the ambient space. In Section <ref>, two quantities m and N will arise in our variational problem and we will work with currents with coefficients in ^m and ^N, respectively. The letter n, used in this preliminary section, stands for the dimension of the vector space of coefficients of our currents. In the sequel one can refer to the definitions of this section replacing n=m or n=N.
 

Currents with coefficients in a normed (abelian) group (G,|·|_G) have been introduced in <cit.> and already studied by several authors (see <cit.>). Our interest is restricted to the case (G,|·|_G)=(^n,·), and we follow a “non-standard” approach, defining currents by duality with ^n-valued differential forms in ^d (instead of completing the space of polyhedral ^n-chains). With this approach we obtain an integral representation of currents, (see (<ref>)) which allows to introduce calibrations in a natural way.


We introduce now some notation about currents with coefficients in (^n,·). For the rest of this section, we will often drop the norm ·, meaning that we will write ^n-valued 1-covector/differential form or 1-current with coefficients in ^n instead of (^n,·)-valued 1-covector/differential 1-form or 1-currents with coefficients in (^n,·). We limit ourselves to define what is strictly necessary for the purposes of our paper. To begin with, we give the following definitions.
A map α: ^d ×^n →
is an ^n-valued 1-covector in ℝ^d if 


  (i) ∀ τ∈ℝ^d, α(τ,·) ∈ (^n)^*;

  (ii) ∀ θ∈^n, α(·,θ): ℝ^d →ℝ is a “classical” 1-covector.

The evaluation of α on the pair (τ,θ) is also denoted by ⟨α;τ,θ⟩. The space of ^n-valued 1-covectors in ^d is denoted by Λ^1(ℝ^d;^n).


Observe that the space Λ^1(ℝ^d;^n) is a normed vector space when endowed with the comass norm 

    α_c:=sup{α(τ,·) ^*: |τ| ≤ 1, τ∈^d}.

We can write the action of an ^n-valued 1-covector α as 

    α(τ,θ)=∑_j = 1^nα_j(τ)⟨ e_j;θ⟩,
 
where, for j=1,…,n, α_j:=α(·, e_j) are the components of α. 

Fix now a convex open set U ⊂ℝ^d. It is clear that such assumption is not restrictive for most of the reasonable cases, nonetheless we remark that other choices of U could change the homology class in which we set the variational problem.
An ^n-valued differential 1-form in U is a map ω:U →Λ^1(ℝ^d;^n). We say that ω is smooth if and only if every component ω_j belongs to C^∞(U;Λ^1(^d;)), where the components of an ^n-valued differential 1-form are defined similarly to the components of an ^n-valued 1-covectors. We denote by C_c^∞(U;Λ^1(ℝ^d;^n)) the vector space of smooth, ^n-valued differential 1-forms, with compact support in U. 


Finally, we define the comass norm of the ^n-valued differential 1-form ω as

    ω_c :=sup_x ∈ Uω(x)_c.

The exterior derivative of an ^n-valued function (0-form) is once again defined using the components.

Let η∈ C_c^∞(U;^n) be an ^n-valued 0-form, and, for j = 1,…,n, denote with η_j its components (i.e., η_j:=⟨η; e_j⟩). Then the exterior derivative of η is the ^n-valued differential 1-form which is defined componentwise by

    (η)_j := (η_j),   j=1,…,n.



We are now ready to define 1-currents with coefficients in ^n.
Let T be a linear functional on C_c^∞(U;Λ^1(ℝ^d,^n)). By definition, T is continuous if T(ω^i)→ 0 for every sequence of ^n-valued differential 1-forms ω^i ∈ C^∞(U;Λ^1(ℝ^d,^n)) such that


  (i) (ω^i) ⊂ K, for some compact set K⊂ U;

  (ii) every component of ω^i converges uniformly to 0 with all its derivatives when i→∞. 

The space of linear, continuous functionals on C_c^∞(U;Λ^1(ℝ^d,^n)) is the space of 1-currents in U with coefficients in ^n
. We write T^i*⇀ T when the sequence of currents (T^i)_i≥ 1 with coefficients in ^n is weakly*-converging to T, i.e. when

    T^i(ω) → T(ω)  ∀ ω∈ C_c^∞(U;Λ^1(ℝ^d,^n)).

Furthermore, if T is a 1-current with coefficients in ^n, we define its mass as 

    (T):=sup{|T(ω)| : ω_c ≤ 1}.


The boundary of T is the ^n-valued distribution ∂ T which fulfills the relation

    ∂ T(η):=T(η)  ∀η∈ C_c^∞(U;^n).
 
Finally, when we mention the components of the current T, we refer to the “classical” currents T_j, j=1,…,n, defined as

    T_j(ω):=T(ω e_j)  ∀ ω∈ C^∞(U;Λ^1(^d;)),

where we denoted by ω e_j the ^n-valued differential 1-form whose j-th component coincides with ω and all other components are all null.




Analogously, the definitions of ^n-valued k-covectors, ^n-valued differential k-forms, and k-currents with coefficients in ^n are given by specifying their components, i.e. an array made of n “classical” k-covectors, differential k-forms, and k-currents, respectively. Similarly, the definitions of the exterior derivative of an ^n-valued differential k-form and of the boundary of a k-current with coefficients in ^n are understood.


Notice that, if T is a current with coefficients in ^m with at most one non-trivial component T_j, then the mass (T) differs from the classical mass of T_j by a multiplicative constant: namely, the ratio between the Euclidean norm on  and the restriction of the norm · on span(e_j). Therefore, to avoid a possibly misleading abuse of notation, we denote 𝕄 the mass of classical currents. 
















We are going to consider the following special class of currents. We recall that a 1-rectifiable set E⊂ U is an ^1-measurable set which can be covered, up to an ^1-null subset, with the images of countably many curves of class C^1. A 1-rectifiable set E has a well defined notion of tangent line at ^1-a.e. point x∈ E, which is denoted Tan(E,x).











A rectifiable 1-current in U, with coefficients in ^n is a 1-current with coefficients in ^n with finite mass admitting the integral representation

    T(ω)=∫_Σ⟨ω(x);ξ(x),θ(x)⟩ d^1(x)  ∀ ω∈ C^∞(U;Λ^1(^d;^n)),

where Σ⊂ U is a countably 1-rectifiable set, ξ(x):Σ→𝕊^d-1∩Tan(E,x) for ^1-a.e. x is called the orientation, and θ∈ L^1_ loc(Σ;^n) is the multiplicity. We denote such current T as Σ,ξ,θ.
 

We have the following characterization of the mass of a rectifiable current (see <cit.> for the analogous statement for “classical” currents).

If T=Σ,ξ,θ is a rectifiable 1-current with coefficients in ^n, then

    (T) = ∫_Σθ(x) d^1(x).



For the rest of the paper, we mainly focus on rectifiable 1-currents with coefficients in ^n whose boundary has finite mass. With a small abuse of notation we call them 1-dimensional integral ^n-currents. The following structure theorem for 1-dimensional integral ^n-currents is an immediate consequence of its counterpart for “classical” integral 1-currents (<cit.>). See also <cit.>). Roughly speaking, it states that a 1-dimensional integral ^n-current can be thought simply as a superposition of oriented curves with (vectorial) multiplicities.



Let T=Σ,τ,θ be a 1-dimensional integral ^n-current in U. Then

    T=∑_k=1^MT̃^k+∑_h=1^∞T^h,

where:


  ∘ T̃^k=Γ_k,τ_k,θ̃_k, being Γ_k the image of an injective, Lipschitz, open curve γ_k:[0,1]→ U, τ_k(γ_k(t))=·γ_k(t)/|·γ_k(t)| for a.e. t, and θ̃_k∈^n being constant on Γ_k. Moreover, for j=1,…,n it holds 

    ∑_k=1^M|(θ̃_k(x))_j|≤1/2𝕄(∂ T_j),  .

Additionally, for j=1,…,n it holds

    |∑_k=1^M⟨τ_k(x);τ(x)⟩(θ̃_k(x))_j|≤ |(θ(x))_j|,

and in the inequality above the two quantities ∑_k=1^M⟨τ_k(x);τ(x)⟩(θ̃_k(x))_j and (θ(x))_j have the same sign.

  ∘ T^h= Z_h,ν_h,θ_h, being Z_h the image of a Lipschitz, closed curve ζ_h:[0,1]→ U, which is injective on (0,1), ν_h(ζ_h(t))=·ζ_h(t)/|·ζ_h(t)| for a.e. t, and being θ_h∈^n constant on Z_h. 





 §.§ Compactness

The following compactness theorem holds:


Consider a sequence (T^l)_l∈ of 1-dimensional integral ^n-currents in U such that

    sup_l∈((T^l)+(∂ T^l))<+∞ .

Then there exists a 1-dimensional integral ^n-current T in U and a subsequence (T^l_r)_r∈ such that

    T^l_r*⇀ T .

Moreover it holds

    lim inf_r→∞(T^l_r)≥(T).


The proof of this result is a straightforward application of the Closure Theorem for integral currents (see <cit.>) to each component T^l_j of the elements of the sequence (T^l)_l∈. The lower semicontinuity of the mass is straightforward. By direct methods we get the existence of a mass-minimizing rectifiable current for a given boundary.


Let T^♭ be a 1-dimensional integral ^n-current in U. Then there exists a 1-dimensional integral ^n-current T^♯ in U such that

    (T^♯)=min_∂ T=∂ T^♭(T) ,

where the minimum is computed among 1-dimensional integral ^n-currents in U.


















 §.§ Calibrations

The main advantage of proving the equivalence between the MMTP and a mass minimization problem is that, in the latter case, we can make use of calibrations to prove minimality.
Consider a rectifiable 1-current T=Σ,τ,θ in U, with coefficients in ^n. A smooth ^n-valued differential 1-form ω in U is a calibration for T if the following conditions hold:


  (i) for a.e. x∈Σ we have that ⟨ω(x);τ(x),θ(x)⟩=θ(x);

  (ii) the form is closed, i.e., dω=0;

  (iii) for every x∈ U, every unit vector τ∈^d and every η∈^n we have that

    ⟨ω(x);τ,η⟩≤η .



The existence of a calibration is a sufficient condition for minimality.

Let T=Σ,τ,θ be a rectifiable 1-current in U, with coefficients in ^n, and let ω be a calibration for T. Then T minimizes the mass among rectifiable 1-currents in U, with coefficients in ^n, with the same boundary ∂ T.


A competitor T'=Σ',τ',θ' satisfies ∂ T'=∂ T. Since U is convex, there exists a 2-dimensional current R in U, with coefficients in ^n, such that ∂ R=T-T'.  As a consequence, together with the properties of ω listed in Definition <ref>, we obtain that

    (T)     = ∫_Σθ(x) d^1(x)
        (i)=∫_Σ⟨ω(x);τ(x),θ(x)⟩ d^1(x)= ∂ R(ω)+T'(ω)
        (ii)=∫_Σ'⟨ω(x);τ'(x),θ'(x)⟩ d^1(x)
        (iii)≤∫_Σ'θ'(x) d^1(x)=(T') .




 In <ref>, we need to allow also the possibility that the competitor Z' is a rectifiable current with coefficients in (^n,·_α). The
existence of a calibration
for Z guarantees the optimality of the mass of Z even in this larger class. The proof of this fact is the same as that given above.






§ MULTI-MATERIAL TRANSPORT PROBLEM

In this section, we define the multi-material transport problem and we state the main result of the paper. First of all, let us introduce some notation. Our ambient is the Euclidean space ℝ^d. 

For n=1,2,…, we consider the following partial order on ^n, where the coordinates are always expressed with respect to the standard basis { e_1,…, e_n}. Given two vectors x=(x_1,…,x_n) and y=(y_1,…,y_n), we write x≼ y if and only if 

    .

We say that a norm · on ℝ^n is monotone if x≤y, for every x ≼ y ∈ℝ^n. We say that · is absolute if x = x̅, ∀ x∈ℝ^n, where x̅ = (|x_1|,…,|x_n|). Now we fix an integer m∈ (which represents the number of different types of commodities involved in the transportation problem).

A multi-material cost is a function :^m→[0,+∞) with the following properties:


  (i)  is even, i.e. (x)=(-x), and (x)=0 if and only if x=0;

  (ii)  is increasing, i.e., (x)≤(y) for every x≼ y;

  (iii)  is subadditive, i.e. (x+y)≤(x)+(y) for every x,y∈^m.

In order to prove the equivalence between the MMTP and a mass minimization problem, we will replace (iii) with a stronger property, namely


  (iii') there exists a monotone norm ·_⋆ on ^m with respect to which  is sublinear, i.e. (x)/x_⋆≤(x')/x'_⋆ for every x,x'∈^m∖{0} with x'≼ x.
 



If  is defined only on a rectangle 
    R:=[-a_1,a_1]×…,×[-a_m,a_m]⊂^m
 and it satisfies (i), (ii), (iii) (respectively (i), (ii), (iii')) on R, then one can define a new cost 
:^m→[0,+∞] defining

    (x):=max_y∈ R{(y):y≼ x}.

One can see immediately that the cost  satisfies (i), (ii), (iii) (respectively (i), (ii), (iii')).















A multi-material cost induces a functional on 1-dimensional integral ^m-currents, that we denote . Given a 1-dimensional integral ^m-current T=Σ,τ,θ, we denote its energy by 


    (T):=∫_Σ(θ) d^1 .







Let us now fix a rectifiable 0-current ℬ on ^d with coefficients in ^m, which is the boundary of a 1-dimensional integral ^m-current. In particular ℬ is represented by the discrete ^n-valued measure 

    ℬ=∑_ℓ=1^M η_ℓδ_p_ℓ,

where p_ℓ are points in ^d, η_ℓ=(η_ℓ,1,…,η_ℓ,m)∈^m and ∑_ℓ=1^M η_ℓ=(0,…,0)∈^m. 

If we read the problem as an optimization problem for the transportation of different goods among factories, the interpretation of ℬ as a given datum should be the following. At each of the M points p_ℓ a certain amount of some of the m materials is produced or requested. A negative sign in the coefficient η_ℓ,i represents the fact that an amount |η_ℓ,i| of the material indexed by i is produced by the factory located at the point p_ℓ, while a positive sign represents the fact that the corresponding amount is requested by that factory.






We are now able to state the multi-material transport problem. Let  satisfy properties (i), (ii), (iii) of Definition <ref>.




  MMTP: Among all 1-dimensional integral ^m-currents T=Σ,τ,θ in ^d such that ∂ T=ℬ, find one which minimizes the energy (T). 






The MMTP admits a solution.


The proof goes through the Direct Method of the Calculus of Variations. The lower semicontinuity of the functional  is stated in <cit.> (see also <cit.>). In <cit.>, we prove the lower semicontinuity in a more general framework in order to obtain the existence of solutions to a “continuous” version of the MMTP. The only issue is that a minimizing sequence {T^l}_l∈ for the MMTP does not necessarily have equi-bounded masses, hence it is not possible to apply Theorem <ref> directly to obtain a minimizer. Nevertheless one can obtain a uniform bound on the masses “removing the cycles” from the T^l's. Namely, writing each T^l=Σ^l,τ^l,θ^l according to Theorem <ref> as 

    T^l=∑_k=1^M(l)(̃T̃^̃l̃)̃^k+∑_h=1^∞(T^l)^h,

and denoting T̃^̃l̃=Σ̃^l,τ^l,θ̃^l :=∑_k=1^M(l)(̃T̃^̃l̃)̃^k,
we get by (<ref>) that for every l∈ it holds θ̃^l≼θ̃^l ^1-a.e. on Σ^l, hence, by the monotonicity of , we deduce that (T̃^̃l̃)≤(T^l). Observing that ℬ=∂ T^l=∂T̃^̃l̃, we have that {T̃^̃l̃}_l∈ is also a minimizing sequence. Moreover, (<ref>) implies that θ̃^l is bounded by a uniform constant M, ^1 a.e. on Σ̃^l, and by properties (i) and (ii) of Definition <ref> the cost of each non-zero element of ^m is bounded from below by a value P. Hence the ratio θ̃^l(θ̃^l) is bounded by C:=M/P ^1 a.e. on Σ̃^l. Integrating on Σ̃^l, we deduce that (T̃^̃l̃)≤ C (T̃^̃l̃).  This allows to apply Theorem <ref> and to find a subsequential limit, which is a solution to the MMTP.


We remark here that, under the additional assumption (iii') on the cost functional, the existence is also a trivial consequence Theorem <ref> below.


The main result of the paper is the fact that, with the additional assumption (iii') on the cost functional, the MMTP is equivalent to the superposition of a certain number of mass minimization problems among 1-dimensional integral currents, with coefficients in a group (which is larger than ^m). Introducing such problems requires some additional notation.

Let ℬ be as in (<ref>). For i=1,…, m, let 

    N_i:=1/2∑_ℓ=1^M|η_ℓ,i|  .


Note that, since |η_ℓ,i| ∈ℕ, ∀ℓ,i, then N_i are natural numbers, for every i, and so is N. Since i represents an index for the m different types of materials, then N_i should be thought as the total amount of the production of the material corresponding to the index i among all factories. Similarly N represents the total amount of production of the union of all materials. We associate to ℬ a rectifiable 0-current, with coefficients in ^N with the following procedure. Heuristically, for every i=1,…, m we will give different labels to each of the N_i copies produced of the i-th material, so that in total we will have N different labels. Note that this is in a certain sense an “unnatural” operation, since in the original problem different copies of the same material are indistinguishable. Let us explain firstly how we assign the labels. We begin by splitting the set {1,…,N} into an ordered sequence made by the m groups {1,…,N_1}, {N_1+1,…,N_1+N_2},…,{N-N_m+1,…,N}. We will use the i-th group (i=1,…,m) as the set of labels for the N_i copies produced of the i-th material. Hence to every index j∈{1,…,N} we associate the corresponding i(j) which is describing to which of the m materials the label j corresponds.


Formally, for every j∈{1,…,N}, we denote i(j) the first index i such that N_1+…+N_i≥ j. 
Now we want to identify one of the points {p_ℓ}_ℓ=1^M in which we will think that the copy of the i(j)-th material, labeled with j, is produced. Therefore we let j̅:=∑_k=0^i(j)-1N_k (observe that j-j̅ describes the position of the index j in the i(j)-th group defined above) and moreover we let ℓ^-(j) be the first index ℓ such that 

    ∑_η_ℓ,i(j)<0 |η_ℓ,i(j)|≥ j-j̅.


Similarly, let ℓ^+(j) be the first index ℓ such that 

    ∑_η_ℓ,i(j)>0η_ℓ,i(j)≥ j-j̅.


Finally we define 

    
 
Since it is too restrictive to assume that, for every j=1,…, N, the i(j)-th material produced in P(j) will be sent to the point D(j), we need to allow some “reshuffling”. To this aim, we let σ=(σ_1,…,σ_m)∈𝒮_N_1×…×𝒮_N_m, where 𝒮_q is the group of permutations on q elements. With a small abuse of notation, we write σ(j) for the number j̅+σ_i(j)(j-j̅). Note that each σ_i (i=1,…,m) is thought as a permutation acting on the i-th group defined above.


Lastly we define our rectifiable 0-current, with coefficients in ^N as

    ℬ_σ:=-∑_j=1^N e_jδ_P_j+∑_j=1^N e_jδ_D_σ(j).


Observe that every fixed permutation prescribes in which of the M points the copy of each labeled material will be moved. Since in our transportation problem it is not natural to prescribe such assignments, we will let the permutation vary.

Now we can state our alternative formulation of the multi-material transport problem, which is simply a mass-minimization problem:


  MMP: Let · be a norm on ^N. Among all σ∈𝒮_N_1×…×𝒮_N_m and among all 1-dimensional integral ^N-currents T̅=Σ̅,τ̅,θ̅ in ^d such that ∂T̅=ℬ_σ (defined in (<ref>)), find one which minimizes the mass (T̅), where the mass is computed with respect to the norm ·. 


The main result of the paper is the following

Let ℬ be as in (<ref>) and N as in (<ref>). Then, for every  as in Definition <ref>, satisfying (i),(ii),(iii'), there exists a norm · on ^N such that the problems MMTP and MMP are equivalent. Namely the minima are the same and moreover there is a canonical way to construct a solution of the MMTP from a solution of the MMP and vice versa.



A corollary of the proof of Theorem <ref> is the following. If there exists one index ℓ̅∈{1,…,M} such that |η_ℓ̅,i|=∑_ℓ≠ℓ̅ |η_ℓ,i|, for every i=1,…,m, then in the MMP it is not necessary to minimize among the permutations σ (i.e. the minimum is the same for every permutation). In the “single-material” case, the assumption corresponds to the case called “irrigation problem”, where the initial (or the target) measure is a Dirac delta.



Recalling the interpretation of the coordinates of ^N as labels for different copies of the m materials, we can view the MMP as a version of the MMTP where one can trace the trajectory of every particle of each type of material. The equivalence between Eulerian formulations (describing the flow of particles at every point) and Lagrangian formulations (describing the particles' trajectories) of branched transportation problem is an interesting problem in general (see e.g. <cit.>) which is based on a profound result of Smirnov on the structure of classical normal 1-currents (see <cit.>). For our discrete problem, instead, the equivalence is a simple consequence of Theorem <ref>. For the sake of brevity, we will not pursue this in the present paper.













§ EQUIVALENCE BETWEEN MMTP AND MMP


The aim of this section is to establish the equivalence between the MMTP and the MMP of Section <ref>. This follows from Theorem <ref>, once we find a norm · on ^N which is monotone and satisfies, for every σ∈𝒮_N_1×…×𝒮_N_m,

    (θ_1,…,θ_m)=(θ_1)∑_j=1^|θ_1|e_σ(j)+(θ_2)∑_j=N_1+1^N_1+|θ_2|e_σ(j)+…+(θ_m)∑_j=N-N_m+1^N-N_m+|θ_m|e_σ(j),

where N and N_i (i=1,…, m) are defined in (<ref>). The existence of such norm would imply that the cost of the transportation of a vector of materials (θ_1,…,θ_n) along a stretch of the network corresponds to the mass of the current with coefficients in ^N that we will associate to that stretch of the network.

The existence of such norm is proved in Theorem <ref>. Firstly we show how to prove Theorem <ref> using the existence of ·.
 Fix ℬ as in (<ref>). We divide the proof in two steps.


Step 1: from MMTP to MMP. Let T:=Σ,τ,θ be a 1-dimensional integral ^m-current which is a competitor for the MMTP. The aim of this step is to construct from T a competitor T̅ for the MMP “associated” to ℬ, such that (T̅)≤ (T). 

Consider the components of T (see Figure <ref>) 

    T_1:=Σ,τ,θ_1,…,T_m:=Σ,τ,θ_m.
 



By <cit.> we can write, for i=1,…,m 

    T_i=∑_k=1^N_iT̃_i^k+∑_h=1^∞T_i^h,

with[Observe that all the currents in (<ref>) are “classical” currents, therefore the notion of mass is the standard one.] 

    𝕄(T_i)=∑_k=1^N_i𝕄(T̃_i^k)+∑_h=1^∞𝕄(T_i^h)  ,

where:


  ∘ T̃_i^k:=Γ_i^k,τ_i^k,1 are integral 1-currents associated to simple, Lipschitz, open curves γ_i^k:[0,1]→^d, where Γ_i^k:=(γ_i^k) and τ_i^k:=(γ_i^k)'/|(γ_i^k)'|;

  ∘ T_i^h:= Z_i^h,ν_i^h,1 are integral 1-currents associated to simple, Lipschitz, closed curves (cycles) ζ_i^h:[0,1]→^d, where Z_i^h:=(ζ_i^h) and ν_i^h:=(ζ_i^h)'/|(ζ_i^h)'|.


For every i=1,…,m, denote by Σ_i:=∪_k=1^N_iΓ_i^k and by T' the 1-current 

    T_i':= ∑_k=1^N_iT̃_i^k.

Since each T_i' is supported on Σ, we can write T_i':=Σ,τ,θ_i'. Let T' be the 1-dimensional integral ^m-current whose components are (T'_1,…,T'_m). 

It follows from (<ref>) that for every i=1,…,m and for ^1-a.e. x∈Σ it holds 

    θ_i(x)=∑_k=1^N_iχ_Γ_i^k(x)⟨τ_i^k(x);τ(x)⟩+∑_h=1^∞χ_Z_i^h(x)⟨ν_i^h(x);τ(x)⟩,

where we denoted by χ_E the characteristic function of the set E taking values 0 and 1. 
 Combining (<ref>) and (<ref>) we deduce that for every i=1,…, m it holds 


    τ_i^k(x)=(θ_i(x))τ(x),

and

    ν_i^h(x)=(θ_i(x))τ(x),   .
 
Hence it holds (θ_1'(x),…,θ_m'(x))≼(θ_1(x),…,θ_m(x)), for ^1-a.e. x∈Σ, which yields (T')≤(T), by property (ii) of Definition <ref>. Moreover by (<ref>) it holds ∂ T'=∂ T.



Next we associate to T' a 1-dimensional integral ^N-current T̅, simply defining T̅ to be the current with components (T̅_1,…, T̅_N), where we set, for j=1,…, N (recalling the definition of i(j) and j̅ from <ref>) T̅_j:=T̃_i(j)^k, .




Applying the boundary operator to (<ref>), it follows that T̅ is a competitor for the MMP. Moreover by (<ref>) and (<ref>) it follows that (T̅)=(T')≤(T).


Step 2: from MMP to MMTP. Let σ∈𝒮_N_1×…×𝒮_N_m. Let T̅:=Σ̅,τ̅,θ̅ be a 1-dimensional integral ^N-current which is a competitor for the MMP and in particular ∂T̅=ℬ_σ (defined in (<ref>)). The aim of this step is to construct from T̅ a competitor T for the MMTP associated to ℬ, such that (T)≤ (T̅).

Let 

    T̅_1:=Σ̅,τ̅,θ̅_1,…, T̅_N:=Σ̅,τ̅,θ̅_N
 
be the components of T̅ (see Figure <ref>).  

As in the previous step, by <cit.> and using the fact that (∂T̅_j)=2, we can write for j=1,…,N 

    T̅_j= T̃_j+∑_h=1^∞T_j^h,

with 

    𝕄(T̅_j)=𝕄(T̃_j)+∑_h=1^∞𝕄(T_j^h),

where:


  ∘ T̃_j:=Γ_j,τ_j,1 are integral 1-currents associated to simple, Lipschitz, open curves γ_j:[0,1]→^d, where Γ_j:=(γ_j) and τ_j:=(γ_j)'/|(γ_j)'|;

  ∘ T_j^h:= Z_j^h,ν_j^h,1 are integral 1-currents associated to simple Lipschitz closed curves ζ_j^h:[0,1]→^d, with ζ(0)=ζ(1), where Z_j^h:=(ζ_j^h) and ν_j^h:=(ζ_j^h)'/|(ζ_j^h)'|.

  Let T' be the 1-dimensional integral ^N-current whose components are (T̃_1,…,T̃_N). By (<ref>) and (<ref>), for j=1,…, N it holds ⟨τ̅;τ̃_j⟩=(θ̅_j) ^1-a.e. in Γ̃_j and hence, since · is a monotone norm, we have (T')≤(T̅). Moreover, by (<ref>) it holds ∂ T'=∂T̅.


Let T be the 1-dimensional integral ^m-current with components (recalling the definition of i(j) from <ref>)

    T_i:=∑_j:i(j)=iT̃_j.


Since ∂ T'= ℬ_σ, then ∂ T=ℬ. Moreover by (<ref>) it holds (T)=(T')≤(T̅).


We conclude this section by proving the existence of a monotone norm · satisfying (<ref>).

In the proof of the next theorem, we will use the following fact, which can be found in <cit.>. Recall the notions of monotone and absolute norm given at the beginning of Section <ref>, as well as the partial order introduced there. 


An absolute norm on ℝ^n is monotone.


We will use the term orthant in ℝ^n for the following subset of ℝ^n. Consider a vector ξ∈ℝ^d whose coordinates are only ± 1. The ξ-orthant is:

    {x ∈ℝ^d: ξ_ℓ x_ℓ≥ 0, ∀ℓ=1,…,n}.

Note that an orthant is always closed.


Let :^m→[0,+∞) be a function satisfying (i), (ii), (iii') of Definition <ref>. Let ℬ be as in (<ref>) and let N and N_i (i=1,…, m) be the natural numbers defined in (<ref>). Then there exists a monotone norm · on ^N satisfying (<ref>).



Step 1: First of all, let us suppose that  has the additional property that

    (x) = (x̅)

for every x∈^m, where we used the notation introduced at the beginning of Section <ref>. 



General strategy



Let us denote by 𝒜 the set of elements of ^N whose coordinates are only 0's and 1's, and denote 𝒜̅ := {x ∈ℤ^N: x̅∈𝒜}.

Let A = (a_1,…,a_N), B = (b_1,…,b_N) ∈𝒜. We say that the pair (A,B)∈𝒜×𝒜 is good if A-B≠ 0 and the following implications hold, for every i=1,…,m (again, we set N_0:=0):


  ∘ if a_j=1 for some j between N_1+…+N_i-1+1 and N_1+…+N_i then b_h=0 for all indices h in the same range;

  ∘ if b_j=1 for some j between N_1+…+N_i-1+1 and N_1+…+N_i then a_h=0 for all indices h in the same range.

Recalling the heuristic interpretation described in Section <ref>, any vector of ^N whose coordinates are only -1,1, or 0, represents a collection of labelled materials, possibly of different types. If (A,B) is a good pair, then on each of the m groups into which we split the set of labels {1,…,N} at most one among A and B can have some non-zero coordinates. Therefore in the corresponding vector A-B, all the coordinates in each group  belong either to {0,1} or to {0,-1}. This represents the fact that all the materials of the same type are assumed to travel with the same orientation.

If (A,B) is a good pair we define

    c_A,B:=(∑_j=1^N_1(a_j-b_j),…,∑_j=N-N_m-1+1^N(a_j-b_j)).
 
This represents the cost of transporting the collection of goods labeled by A-B along a stretch of unit length.
Observing that, if A - B≠ 0 we have c_A,B≠ 0, we can define

    q_A,B:=A-B/c_A,B,

for any good pair (A,B). Observe that if (A,B) and (A',B') are good pairs with A-B=A'-B', then by (<ref>) it holds c_A,B=c_A',B'. Hence given D≠ 0 any vector in 𝒜̅, it is convenient to define c_D:=c_D̅,0, which is well defined since (D̅,0) is a good pair. As above, we define q_D:=D/c_D. 

Consider the convex hull 

    C:=({q_D: D∈𝒜̅∖{0}})⊂^N.
 
The theorem is proven if we show three properties of C:


  (1) C is a convex body (i.e. the closure of its non-empty interior) which is bounded and symmetric with respect to the origin;

  (2) C is a monotone set, i.e. for every x,y∈^N, with y≼ x, if x∈ C, then also y∈ C.

  (3) it holds

    q_A,B∈∂ C,  ∀ A,B∈𝒜,  .

 
Indeed, if (1) holds, there exists a norm · on ^N whose unit ball is the set C. Then, (2) implies that · is monotone. Moreover (3) implies that · satisfies (<ref>). Indeed, take an m-tuple (θ_1,…,θ_m) and denote, for every i=1,…, m, θ_i^+:=max{θ_i,0}, θ_i^-:=max{-θ_i,0}. Now define for every σ∈𝒮_N_1×…×𝒮_N_m,

    A_σ:=θ_1^+∑_j=1^|θ_1|e_σ(j)+θ_2^+∑_j=N_1+1^N_1+|θ_2|e_σ(j)+…+θ_m^+∑_j=N-N_m+1^N-N_m+|θ_m|e_σ(j)
 
and

    B_σ:=θ_1^-∑_j=1^|θ_1|e_σ(j)+θ_2^-∑_j=N_1+1^N_1+|θ_2|e_σ(j)+…+θ_m^-∑_j=N-N_m+1^N-N_m+|θ_m|e_σ(j).
 
One can verify that A_σ,B_σ∈𝒜 and (A_σ,B_σ) is a good pair. Hence we have 

    1(3)=q_A_σ,B_σ=A_σ-B_σ/c_A_σ,B_σ(<ref>)=A_σ-B_σ/(θ_1,…,θ_m).

We conclude noting that A_σ-B_σ coincides with the RHS of (<ref>).



Proof of (1) and (2)




To prove (1), notice that for every j=1,…,N, q_± e_j are contained in C, hence 0∈ int(C). The fact that C is symmetric with respect to the origin follows from the fact that the multi-material cost  is even. Finally, the boundedness is trivial, since C the convex hull of a finite set. 

We will now prove (2), i.e. that C is a monotone set. To prove it, we show that the norm with unit ball C is absolute. This implies the monotonicity by Lemma <ref>. Let x ∈ℝ^N, with x=1. The fact that x = 1 implies that x ∈∂ C⊂ C, therefore we can write

    x = ∑_k=1^K t_kq_D^k,

where D^k∈𝒜̅∖{0}, ∑_k=1^K t_k = 1, with t_k positive.
There exists a diagonal matrix M∈ Mat^N× N with entries 1,-1,0 such that Mx = x̅. Therefore:

    x̅=Mx = ∑_k=1^K t_kMq_D^k =∑_k=1^K t_k q_MD^k≤∑_k=1^K t_kq_MD^k≤∑_k=1^K t_k≤ 1,

where the third equality follows from the fact that c_D^k=c_MD^k (the latter being a consequence of the fact that MD=D for every D∈𝒜̅∖{0}) and the second inequality follows from the fact that q_D≤ 1, ∀ D∈𝒜̅, by the definition of C. This proves that 
    x̅≤x,   ∀ x∈^N.
 The proof of the reverse inequality is analogous.




Proof of (3)




The proof of (3) is more involved. We can prove equivalently that for every A,B∈𝒜, such that (A,B) is a good pair, and for every t>0 the following implication holds


    tq_A,B∈ C⟹ t≤ 1.

Since tq_A,B∈ C, we can write

    tq_A,B=∑_k=1^Kλ_kq_D^k,

where D^k∈𝒜̅, ∑_k=1^Kλ_k = 1, with λ_k positive. Formula (<ref>) can be rewritten componentwise, denoting D^k = (d^k_1,…,d^k_N),

    ta_j - b_j/c_A,B=∑_kλ_kd^k_j/c_D^k,  for every  j=1,…,N.

For k=1,…,K, we define vectors F^k:=(f^k_1,…,f^k_N)∈𝒜̅ by

    f^k_j := 0,  if a_j - b_j = 0
    
    f^k_j := d^k_j,  otherwise.

Note that

    ta_j - b_j/c_A,B=∑_kλ_kf^k_j/c_D^k,  for every  j=1,…,N.


Indeed, the equality 
    ∑_kλ_kd^k_j/c_D^k = ∑_kλ_kf^k_j/c_D^k
 holds for those j such that ∑_kλ_kd^k_j/c_D^k≠ 0 because in that case f_j^k = d_j^k for every k. On the other hand, for those indices j for which ∑_kλ_kd^k_j/c_D^k = 0 by the definition of F^k, also f_j^k = 0 for every k, so that

    ∑_kλ_kf^k_j/c_D^k=0 = ∑_kλ_kd^k_j/c_D^k.



 f_j^k might differ from d_j^k (and it is equal to zero for every k) only in correspondence of those indices j where ∑_kλ_kd^k_j/c_D^k=0.


Moreover

    c_F^k≤ c_D^k
 
by property (ii) in Definition <ref> (because F̅^k≼D̅^k by definition of F^k).




Denote, for i=1,…,m,

    x_i := ∑_j = N_1 + … + N_i - 1 + 1^N_1 + … + N_ia_j - b_j,

and for k=1,…, K,

    x^k_i := ∑_j = N_1 + … + N_i - 1 + 1^N_1 + … + N_ie^k_j.

Define, for every k = 1,…,K and for every i=1,…,m,

    y^k_i:=
    
    x^k_i,  if  x^k_ix_i ≥ 0
    
    -x^k_i,  if  x^k_ix_i ≤ 0.


Finally, denote x:= (x_1,…,x_m), and y^k:= (y_1^k,…,y_m^k), for k=1,…,K. By (<ref>), we have that y^k ≼ x, for every k. To see this, note that, by the definition of y^k, it immediately follows that y_i^kx_i ≥ 0. To prove that |y_i^k|≤|x_i| for every i and k, we recall the fact that (A,B) is a good pair, so that, in particular, we have the following property:

    ∑_j = N_1 + … + N_i - 1 + 1^N_1 + … + N_i|a_j - b_j| = |∑_j = N_1 + … + N_i - 1 + 1^N_1 + … + N_ia_j - b_j|, ∀ i.

Also, since |a_j - b_j| ∈{0,1} for every j, by the definition of f_j^k, it readily follows that

    |f_j^k| ≤ |a_j - b_j|, ∀ j,k.

We also have

    |y_i^k| = |x_i^k| ≤∑_j = N_1 + … + N_i - 1 + 1^N_1 + … + N_i|f^k_j|(<ref>)≤∑_j = N_1 + … + N_i - 1 + 1^N_1 + … + N_i|a_j - b_j| (<ref>)=|∑_j = N_1 + … + N_i - 1 + 1^N_1 + … + N_ia_j - b_j| = |x_i|.
 



Moreover, by (<ref>), for every i=1,…,m it holds

    tx_i/c_A,B = ∑_kλ_kx_i^k/c_D^k,

hence the fact that (y_i^k) = (x_i) implies

    t|x_i|/c_A,B   =t(x_i)x_i/c_A,B = ∑_kλ_k(x_i)x_i^k/c_D^k = ∑_kλ_k(x_i)(x_i^k)|x_i^k|/c_D^k =
       =∑_kλ_k(x_ix_i^k)|y_i^k|/c_D^k = ∑_kλ_k(x_i^k)y_i^k/c_D^k.

From the equality (y_i^k) = (x_i), holding for every k,i, we also deduce that, if we fix i, the quantity (y_i^k) remains constant when varying k.
Now, if y_i^k is positive, for every k, since (x_i^k) ≤ 1, we get

    t|x_i|/c_A,B≤∑_kλ_ky_i^k/c_D^k = |∑_kλ_ky_i^k/c_D^k|.

Otherwise, using the fact that (x_i^k) ≥ -1,

    t|x_i|/c_A,B≤∑_kλ_k-y_i^k/c_D^k = |∑_kλ_ky_i^k/c_D^k|.

We have just proved that

    tx/c_A,B≼∑_k:F^k≠ 0λ_ky^k/c_D^k.

Finally, note also that y̅^k = x̅^k. By (<ref>) it holds c_A,B = (x) and c_F^k = c_F̅^k= (x^k) = (y^k), this implies, by property (iii') of Definition <ref> that

    c_A,By^k_⋆/c_F^kx_⋆ = (x)y^k_⋆/(y^k)x_⋆≤ 1,  ∀ k=1,…,K ,

where ·_⋆ is the norm appearing in such definition. Using that ·_⋆ is monotone, (<ref>) and (<ref>), we get

    tx_⋆≤∑_k:F^k≠ 0λ_kc_A,By^k/c_D^k_⋆≤∑_k:F^k≠ 0λ_kc_A,By^k/c_D^k_⋆ = ∑_k:F^k≠ 0λ_kc_A,By^k_⋆/c_D^k≤∑_k:F^k≠ 0λ_kc_A,By^k_⋆/c_F^k.

Finally, dividing by x_⋆, (<ref>) yields

    t ≤∑_k:F^k≠ 0λ_k ≤ 1.


Step 2:
Now consider a general cost , which does not necessarily satisfy (<ref>). We will construct a closed, convex, and symmetric set C, whose associated norm is monotone and satisfies (<ref>).



General strategy



For any orthant 𝒪⊂^m, we define a cost _𝒪:^m→ [0,+∞), imposing the following properties:


  (a) _𝒪(x)=(x) if x∈𝒪;

  (b) _𝒪(x)=_𝒪(x̅) for every x.

Trivially properties (i),(ii),(iii') of Definition <ref> are satisfied by C_𝒪. 

Let ·_𝒪 be the norm on ^N obtained applying Step 1 to the cost _𝒪 and let B_𝒪 be the unit ball with respect to such norm (see Figure <ref>). Let us take any point x∈int(𝒪) and define 

    σ_𝒪:=((x_1),…,(x_m))∈^m.



Let us also denote

    τ_𝒪:= (x_1)(e_1+…+e_N_1) + … + (x_m)(e_N-N_m+1+…+e_N)∈^N,

and let H_𝒪 be the unique orthant in ^N containing the point τ_𝒪. Finally, consider A_𝒪:=H_𝒪∩ B_𝒪 and (see Figure <ref> and Figure <ref>)

    C_𝒪:={p∈^N:∃ q∈ A_𝒪 (τ_𝒪)_j(p_j-q_j)≤ 0 }.






Observe that 

    C_𝒪∩ H_𝒪=A_𝒪,

by the monotonicity of A_𝒪, which is implied by the monotonicity of B_𝒪 (the intersection of monotone sets is monotone). Lastly we denote 
    C:=⋂_𝒪⊂^mC_𝒪,

where the intersection is taken among the 2^m orthants in ^m (see Figure <ref>).



We claim that C is a closed, convex, and monotone set, with non-empty interior, which is symmetric with respect to the origin, bounded, and satisfies

    C∩ H_𝒪=A_𝒪,  .

The monotonicity of C would imply that the norm · on ^N, whose unit ball is C, is monotone. Moreover, Step 1 implies that (<ref>) holds for the norm ·_𝒪 and the cost 𝒞_𝒪. We also observe that, in the orthant 𝒪 of ^m, the costs 𝒞 and  𝒞_𝒪 coincide. Also, (<ref>) implies that, in the orthant H_𝒪 of ^N, · and ·_𝒪 coincide. In this way, we get that (<ref>) holds also for · and for the cost . 

The fact that C is closed, convex and monotone follows from the fact that each set C_𝒪 is so, moreover each C_𝒪 contains a neighborhood of the origin, hence C has non-empty interior. The fact that C is bounded and symmetric with respect to the origin follows from the fact that C_𝒪∩ C_-𝒪 is so for every 𝒪, where we denoted by -𝒪 the orthant which is symmetric to 𝒪 with respect to the origin. To conclude, we have to prove (<ref>). To prove (<ref>), we make the following claim:

    Claim 1
    A_𝒪'∩ H_𝒪=A_𝒪∩ H_𝒪',  .




Proof of (<ref>) using (<ref>)



Let us show firstly how (<ref>) implies (<ref>). By the definition of C, it is sufficient to show that

    C_𝒪'∩ A_𝒪=A_𝒪,  ,

indeed

    C∩ H_𝒪= ⋂_𝒪'⊂^mC_𝒪'∩ H_𝒪=⋂_𝒪'⊂^mC_𝒪'∩ C_𝒪∩ H_𝒪(<ref>)=⋂_𝒪'⊂^mC_𝒪'∩ A_𝒪(<ref>)=A_𝒪.

To prove (<ref>) using (<ref>), we write

    C_𝒪'∩ A_𝒪 = ⋃_H(C_𝒪'∩ H∩ A_𝒪),

where H varies among the 2^N orthants of ^N. Then (<ref>) would follow from

    C_𝒪'⊇ H∩ A_𝒪,  ∀𝒪,𝒪',H.

To prove (<ref>), consider z ∈ H∩ A_𝒪. We define a new vector, y∈ℝ^N, in this way:

    y_j =
    
    z_j,  if (τ_𝒪')_jz_j ≥ 0, 
    
    0,  otherwise.

It is immediate to see that (τ_𝒪')_j(z_j - y_j) ≤ 0, ∀ j, and that y∈ H_𝒪'. Hence, to prove that z∈ C_𝒪' it is sufficient to prove that y ∈ A_𝒪'. We observe that y ∈ A_𝒪, because y≼ z and z∈ A_𝒪. By (<ref>), this yields: 
    y ∈ A_𝒪∩ H_𝒪'= A_𝒪'∩ H_𝒪.
 Therefore y ∈ A_𝒪' as desired.
 



Proof of (<ref>): strategy



To prove (<ref>), we will prove the more precise formula:

    A_𝒪'∩ H_𝒪 = ({0}∪{q_D:D∈ (𝒜̅∩ H_𝒪∩ H_𝒪'∖{0})}),  ∀𝒪,𝒪' ⊂ℝ^m.

Equation (<ref>) implies (<ref>) because its right hand side does not change if we swap 𝒪 and 𝒪'.
Denote E the RHS of (<ref>), i.e. 

    E:=({0}∪{q_D:D∈ (𝒜̅∩ H_𝒪∩ H_𝒪'∖{0})}),
 and observe that E⊆ A_𝒪'∩ H_𝒪, since q_D ∈ A_𝒪'∩ H_𝒪 for every D ∈𝒜̅∩ H_𝒪∩ H_𝒪'∖{0}, by Step 1.

In order to prove (<ref>), we need to prove the reverse inclusion, hence, since A_𝒪'∩ H_𝒪 is a compact convex set, we can assume by contradiction that (by Krein-Milman Theorem) there exists an extreme point z of A_𝒪'∩ H_𝒪 that does not belong to E.

Since z∈ A_𝒪'⊂ B_𝒪', we can write it as a convex combination

    z=∑_k=1^Kλ_k q_D^k,

where we remind that q_D^k=D^k/c_D^k, D^k∈𝒜̅ and c_D^k:=c_D̅^k,0 are those defined in (<ref>), with _𝒪' in place of .
Our aim is to replace the elements q_D^k appearing in the convex combination above with suitable elements q_F^k, where the points F^k belong to 𝒜̅∩ H_𝒪∩ H_𝒪'. Firstly we will prove only that one can write z as a convex combination of 0 and some points q_G^k, where the points G_k can be chosen in 𝒜̅∩span{H_𝒪∩ H_𝒪'}. Then we will reduce to the points q_F^k with F^k in 𝒜̅∩ H_𝒪∩ H_𝒪' which would give a contradiction to the fact that z∉E.




Proof of (<ref>): first reduction




For k=1,…,K, we define vectors G^k:=(g^k_1,…,g^k_N)∈𝒜̅ by

    g^k_j := 0,  if z_j = 0
    
    g^k_j := d^k_j,  otherwise.

Note that, as a consequence of (<ref>) and the fact that z∈ H_𝒪'∩ H_𝒪, for every k we have that G^k∈𝒜̅∩ span{H_𝒪∩ H_𝒪'}. Moreover

    z=∑_k=1^Kλ_kG^k/c_D^k.

We also have that

    c_G^k≤ c_D^k

by the monotonicity of the cost _𝒪'. Hence we can write, denoting λ'_k:=λ_kc_G^k/c_D^k≤λ_k,

    z=∑_k=1^Kλ'_kq_G^k.

Hence we have written z as a convex combination of 0 and some q_G^k, for points 

    G^k∈𝒜̅∩span{H_𝒪∩ H_𝒪'}.





Proof of (<ref>): second reduction



Let now η:=(η_1,…,η_N) be a point in the relative interior of H_𝒪∩ H_𝒪'.
Note that one can choose η = τ_𝒪 + τ_𝒪'. Indeed, the relative interior of H_𝒪∩ H_𝒪' is the set of points p = (p_1.…,p_N)∈^N such that

    p_j = 0,  if  (τ_𝒪)_j(τ_𝒪')_j = - 1,
    (p_j) = (τ_𝒪)_j,  if  (τ_𝒪)_j(τ_𝒪')_j = 1.

For k=1,…,K, we define vectors F^k:=(f^k_1,…,f^k_N)∈𝒜̅ by

    f^k_j := g^k_j,  if η_jg^k_j ≥ 0
    
    f^k_j := -g^k_j,  otherwise.

Since, for every k, G^k∈𝒜̅∩ span{H_𝒪∩ H_𝒪'}, then F^k∈𝒜̅∩ H_𝒪∩ H_𝒪'. Indeed H_𝒪∩ H_𝒪' is the set of points p = (p_1,…,p_N)∈ span{H_𝒪∩ H_𝒪'}⊂^N such that p_jη_j ≥ 0 for every j. Since z∈ H_𝒪∩ H_𝒪' and, since _𝒪' satisfies (<ref>), it holds c_G^k=c_F^k for every k, then

    z=∑_k=1^Kλ'_kq_G^k≼∑_k=1^Kλ'_kF^k/c_G^k=∑_k=1^Kλ'_kq_F^k=:z',

where we remind that ≼ is the order relation defined in (<ref>). 



Proof of (<ref>): last contradiction, i.e. z=z'



We observe that by (<ref>) and since F^k∈𝒜̅∩ H_𝒪∩ H_𝒪' it follows that z'∈ E.
We will prove now that z'=z, which would be a contradiction, since z∉E by assumption. Assume by contradiction that z'≠ z and observe that 

    z_j = 0  for some  j ⇒ z_j' = 0.

Indeed, (<ref>) yields that g_j^k = 0 for every k, if z_j = 0, and then by (<ref>) also f_j^k = 0. Therefore, by (<ref>), 
    z'_j = ∑_k=1^Kλ'_kf_j^k/c_F^k = 0.

Define now, for ε>0, w_ε:=z-ε(z'-z). Note that, by (<ref>), we have w_ε≼ z≼ z' for ε sufficiently small. This implies that, for ε sufficiently small, w_ε∈ A_𝒪'∩ H_𝒪, because A_𝒪'∩ H_𝒪 is an intersection of monotone sets, therefore monotone. Hence we can write z as a non-trivial convex combination of the points w_ε and z' in A_𝒪'∩ H_𝒪, which violates the extremality of z.  







































As we observed before, Theorem <ref> provides a proof of the existence of a solution to the MMTP, which does not require a proof of the lower semicontinuity of the energy 𝔼.
 Under assumptions (i),(ii),(iii') on the cost functional , the problems MMTP and MMP admit a solution. 


The fact that the MMP admits a solution follows from Theorem <ref>. The fact that the MMTP admits a solution then follows from Theorem <ref>.


The property (iii') of Definition <ref> appears to be the most restrictive. However, at least in the “single-material” case is also necessary to obtain the equivalence with the mass-minimization problem.


If m = 1, and 𝒞 is a cost that fulfills (i),(ii) of Definition <ref>, then (iii') holds if and only if there exists a monotone norm · that satisfies (<ref>).


One implication has already been proven in Theorem <ref>. Suppose now that there exists a monotone norm · on ℝ^N that satisfies (<ref>). Fix any E ∈𝒜, where 𝒜 is defined at the beginning of the proof of Theorem <ref>. We can write E as

    E = ∑_k ∈ K e_i_k,

being K a subset of {1,…,N}. We denote with #K the cardinality of K. By (<ref>), we have:

    E = 𝒞(#K) = F,

for any F∈𝒜 such that F = ∑_k ∈ K' e_i_k and #K' = #K. For every ℓ∈ K define K_ℓ := K∖{ℓ}.
Define E_ℓ := ∑_k ∈ K_ℓ e_i_k.
Therefore,

    (#K - 1)E = ∑_ℓ∈ K E_ℓ,

and, by (<ref>), we get

    (#K - 1)𝒞(#K)= (#K - 1)E = ∑_ℓ∈ K E_ℓ≤∑_ℓ∈ K E_ℓ= ∑_ℓ∈ K𝒞(#K - 1) = #K𝒞(#K - 1).


Since K⊂{1,…,N} is arbitrary, we obtain, ∀ x ∈{2,…,N},


    C(x)/x≤C(x - 1)/x - 1,

and, by induction,

    C(x)/x≤C(y)/y,  if  1≤ y ≤ x.


It is well-known that, if 𝒞: [0,∞)→[0,∞) is concave and (0)=0, then the quantity 𝒞(x)/x is non-increasing. Hence we obtain the following corollary.

In the case m = 1, Theorem <ref> holds if (iii') is replaced by the request that 𝒞 coincide on  with a concave function.


The previous corollary allows us to include in the list of cost functionals for which Theorem <ref> applies the cost considered in <cit.>, which describes a model for the urban planning (or a discrete version of it, in our case). More precisely the cost is (z)=min{az;z+b} with a>1, b>0, which is clearly concave.




§ PROPERTIES OF MINIMIZERS

Most of the regularity properties for classical continuous models of single-material branched transportation, such as single-path properties and finite tree structure away from the boundary (see <cit.>) are deduced using a crucial property of discrete optimal networks, which is the absence of cycles. Even in our case, removing cycles from each of the m components of a competitor for the MMTP does not increase the energy (note that we have used this fact in the proof of Theorem <ref>). Nevertheless it might happen that the operation does not strictly reduce the energy as well, and in particular minimizers could contain cycles. The aim of this section is to provide a simple example of such phenomenon. 

Consider the multi-material cost

    (θ_1,θ_2,θ_3,θ_4) = max{|θ_1| + |θ_2| + |θ_3|, |θ_4|}.

Since the cost is additive in the first three variables, it follows that, for every boundary datum ℬ whose fourth component is trivial, a solution to the associated MMTP can be obtained as a superposition of the solutions of three single-material problems (see Remark <ref>). Namely those minimization problems whose boundaries are defined respectively by the three components ℬ_1, ℬ_2, and ℬ_3 of ℬ (and the corresponding single-material cost is simply (θ)=|θ| for θ∈).

Let us now fix a specific boundary ℬ.

Let us start with the following simple proposition.

Let 
    ℬ = ∑_ℓ = 1^Mη_ℓδ_x_ℓ
 be a 0-rectifiable current on ^d with coefficients in ^m. Consider a multi-material cost 𝒞:^m→ℝ of the form

    𝒞(θ_1,…,θ_m) = ∑_i = 1^m_i(θ_i),

where every function 𝒞_ℓ:ℤ→ℝ is a multi-material cost for m = 1. Denote also with _i the energy associated to the cost _i, with (·) the energy to (·) and with ℬ_i = ∑_ℓ = 1^Mη_ℓ,iδ_x_ℓ. Then, if T^min_i is the minimizer for the problem

    P_imin_T: ∂ T = ℬ_i_i(T),

the 1-dimensional integral ℤ^m-current T that in components is T = (T^min_1,…, T^min_m) is a minimizer for the problem

    Pmin_S: ∂ S = ℬ(S).



Choose any competitor of the problem (<ref>). Let this be R, with components R = (R_1,…,R_m). Write also R =  E, θ, ξ and R_i=  E, θ_i, ξ, being θ = (θ_1,…,θ_m) ∈^m. Analogously, we write T = Σ, α,τ and T^min_i = Σ,α_i,τ. Observe that every classical integral 1-current R_i is a competitor for the problem (<ref>). Therefore,

    (R) =   ∫_E(θ(x))d^1(x) = ∑_i = 1^m∫_E_i(θ_i(x))d^1(x) = ∑_i =1^m_i(R_i) ≥
       ∑_i = 1^m(T_i^min) = ∑_i = 1^m∫_Σ_i(α_i(x))d^1(x) = ∫_Σ(α(x))d^1(x) = (T).



Take three non-collinear points x_1, x_2, and x_3 on ^2 and denote

    ℬ:=(-1,0,1,0)δ_x_1+(1,-1,0,0)δ_x_2+(0,1,-1,0)δ_x_3.

By the discussion above, a minimizer for the MMTP associated to the cost  for the boundary ℬ is the 1-dimensional integral ^4-current T, which is written in component as T:=(T_1,T_2,T_3,0), where


  (i) T_1:=x_1x_2,τ_1,1 is the classical integral current associated to the segment x_1,x_2 oriented from x_1 to x_2 with unit multiplicity; 

  (ii) T_2:=x_2x_3,τ_2,1;

  (iii) T_3:=x_3x_1,τ_3,1.

Observe also that the 1-dimensional integral ^4-current T':=(T_1,T_2,T_3,T_1+T_2+T_3) satisfies (T')=(T), and since ∂(T_1+T_2+T_3)=0, it follows that ∂ T'=∂ T, hence T' is also a minimizer of the MMTP associated to ℬ. Observe that not only T' contains a topological cycle in its support (that property holds for T itself), but the fourth components of T' contains a cycle (actually it is a cycle) in the sense of currents.

One could find this example unsatisfactory, because the material associated to the cyclic component of T' does not appear in the boundary datum. Nevertheless it is easy to modify the example above in order to add the fourth material in the boundary datum, still obtaining the previous phenomenon. More precisely, denoting T_4 a non-trivial oriented segment which is “very far” from the supports of T_1,T_2, and T_3, then clearly the current T”:=T'+(0,0,0,T_4) is also a minimizer for the corresponding boundary: roughly speaking, even if  in general it would be convenient for the fourth material to interact with the first three, there is no convenience in this case, due to the large distance of the corresponding sources and sinks (see Figure <ref>).  



As it was observed in <cit.>, in order to get better properties of minimizers of single-material branched transportation problem it is necessary to require the concavity of the cost. In our case we will require that the cost is concave in every component. In this case it is possible to prove that there exists a solution T of the MMTP whose components T_i (i=1,…,m) are all supported on trees (in particular they are acyclic currents). Let us stress that this does not imply the absence of loops in the support of T, but only in the support of each T_i. More precisely, we have the following two propositions, which are the analogue of <cit.>. The proofs are also analogous. We say that a multi-material cost :^m→ is concave (resp. strictly concave) if it coincides on ^m with a function f:^m→ which is concave (resp. strictly concave) in every component, i.e. f(z_1,…,z_m) is a concave (resp. strictly concave) function of each variable z_i. We call a tree a set in ^d which does not contain the support of any non-trivial closed curve.

Let  be a concave multi-material cost. Then for every 1-dimensional integral ^m-current T, there exists another current T' with ∂ T'=∂ T, (T')≤(T), and T'_i is supported on a tree for every i=1,…,m. 




Let  be a strictly concave multi-material cost. Then for every 1-dimensional integral ^m-current T which is a solution to the MMTP associated to its boundary, every component T_i of T is supported on a tree. 





With the previous proposition, we can readily find an energy whose minimizer admits a "loop". Consider the following 0-rectifiable current ℬ on ^2 with coefficients in ^4 as boundary: write ℬ = ∑_ℓ = 1^5η_ℓδ_x_ℓ with


  * x_1,x_2,x_3 are the vertices of a non-degenerate triangle (so, in particular do not lie on a line) with x_i - x_j = 1, i≠ j;

  * x_4,x_5 are distinct point with with x_4 - x_5 = 1, very distant from x_1, x_2, x_3. Let us write D for the quantity D := min{x_α - x_i:α =4,5,i = 1,2,3};

  * η_1 = (1,-1,0,0), η_2= (0,1,-1,0), η_3 = (-1,0,1,0), η_4 = (0,0,0,1), η_5 = (0,0,0,-1).

Consider as a multi-material cost

    (θ_1,θ_2,θ_3,θ_4) = max{|θ_1| + |θ_2| + |θ_3|, |θ_4|},

and as usual denote its energy with (·). The minimizer for the problem

    min_S: ∂ S = ℬ(S)

is given by the 1-dimensional integral ℤ^4-current T = (T_1,T_2,T_3,T_4), where


  * T_1 is the current representing the segment joining x_3 and x_1 with multiplicity 1;

  * T_2 is the current representing the segment joining x_1 and x_2 with multiplicity 1;

  * T_3 is the current representing the segment joining x_2 and x_3 with multiplicity 1;

  * T_4 is the current representing the segment joining x_5 and x_4 with multiplicity 1;

To see that T is a minimizer for D sufficiently large, we do the following. Fix D ≥ 10(T). Consider any competitor S = Σ,θ,ξ with θ = (θ_1,θ_2,θ_3,θ_4), rewritten in components as S = (S_1,S_2,S_3,S_4). There exists an open ball A_R of radius R (independent of S and D) containing x_1, x_2, x_3 and for which x_4 and x_5 lie in the interior of the complementary such that the following hold: if ((S_1)∪(S_2)∪(S_3)) ∩ A_R^c ≠∅ or (S_4) ∩ A_R ≠∅, then

    (S) > (T).

This implies that such a current S cannot be a minimizer. Hence, a necessary condition to be a minimizer for S is that θ_4(x) = 0 for ^1⌞ A_R a.e. x and θ_i(x) = 0 for ^1⌞ A_R^c a.e. x, for i = 1,2,3. If we consider a competitor S with the previous property and denote with θ_1 = |θ_1| + |θ_2| + |θ_3| + |θ_4|, we can write: 

    ∫_Σ𝒞(θ_1,θ_2,θ_3,θ_4)d^1 =    ∫_Σ∩ A_R𝒞(θ_1,θ_2,θ_3,θ_4)d^1
    + ∫_Σ∩ A_R^c𝒞(θ_1,θ_2,θ_3,θ_4)d^1=
       ∫_Σ∩ A_R𝒞(θ_1,θ_2,θ_3,0)d^1 + ∫_Σ∩ A_R^c𝒞(0,0,0,θ_4)d^1=
       ∫_Σ∩ A_R|θ_1| + |θ_2| + |θ_3|d^1 + ∫_Σ∩ A_R^c|θ_4|d^1 =
       ∫_Σ∩ A_Rθ_1d^1 + ∫_Σ∩ A_R^cθ_1d^1 =∫_Σθ_1d^1.

Call _1 the energy with associated multi-material cost θ_1. By Proposition <ref>, we deduce that

    min_R: ∂ R = ℬ_1(R) = (T),

and by our previous computation,

    min_S: ∂ S = ℬ(S) ≥min{(T),min_R:∂ R = ℬ(R)} = (T).

This proves that T is the minimizer of our problem. Now, if we add to T the 1-dimensional integral ^4-current R representing the integration along the boundary of the triangle with multiplicity (0,0,0,1), we have that

    ∂ R = 0  and (T + R) = (T).

Therefore, T + R is a minimizer for the multi-material transport problem with boundary ℬ with a component creating a loop. We notice in addition that the cost

    (θ) = max{|θ_1| + |θ_2| + |θ_3|,|θ_4|}
 
defines a monotone norm on ^4 . Therefore, (·) also fulfills property (iii') of Definition <ref>.




§ EXAMPLES


In this section, we consider some concrete costs functional  and we exhibit a possible norm · which turns a MMTP associated to such cost into a mass-minimization problem. At the end of the section we also provide some examples of calibrations. 



 §.§ Examples of costs



  (1) Steiner energy. For m=1, let 

    (z):=
    
    0,     z = 0,
    
    1,     z ≠ 0.

The minimization of the energy  associated to such cost corresponds to the minimization of the size functional. Clearly the corresponding norm · on ^N given by Theorem <ref> is simply the supremum norm.


  (2) Gilbert-Steiner energy. For m=1, fix 0≤α≤1 and let

    (z):=
    
    0,     z = 0,
    
    |z|^α,     z ≠ 0.

The minimization of the corresponding energy  corresponds to the minimization of the α-mass (see e.g. <cit.>). As it is shown in <cit.>, the corresponding norm · on ^N is the p-norm with p=1/α.  Note that for α=0 we recover the Steiner energy.


  (3) Linear combinations. For m=1, fix K∈ and for k=1,…, K let 0≤α_k≤1 and let λ_k>0. Define

    (z):=
    
    0,     z = 0,
    ∑_k=1^Kλ_k|z|^α_k,     z ≠ 0.

It is easy to see that  satisfies properties (i),(ii), and (iii') of Definition <ref>. The corresponding norm · on ^N is x=∑_k=1^Kλ_k|x|^p_k, where p_k=1/α_k. Such a cost is considered for example in <cit.> in order to approximate the Steiner energy and to perform numerical simulations. 



  (4) Supremum of costs. For m=1, fix K∈ and for k=1,…, K let _k be a cost functional satisfying properties (i),(ii), and (iii') of Definition <ref>. Define

    (z):=max_k=1,…,K_k(x).

The corresponding norm · on ^N is the maximum of the norms associated to each _k. 

  (5) PLC technology. For m=2, let 0<α_1≪α_2≤ 1. Define

    (z_1,z_2):=max{λ_1|z_1|^α_1;λ_2|z_2|^α_2},

with λ_1,λ_2>0. A monotone norm · on ^N which satisfies (<ref>) is 

    (x_1,…,x_N_1,y_1,…,y_N_2)=max{λ_1|(x_1,…,x_N_1)|_p_1;λ_2|(y_1,…,y_N_2)|_p_2}.

where p_i=α_i^-1 for i=1,2. The fact that α_1≪α_2 express the idea that once the infrastructure transporting the second material (i.e., the electricity) is built one can add “almost any” quantity of the first material (i.e., Internet signal) for free.

  (6) Composite multi-material costs. For general m≥ 2, consider any monotone norm |·|_⋆ in ^m and single-material costs _1,…,_m: →, associated to monotone norms ·^1, …, ·^m on ^N_1,…,^N_m, respectively. Define

    (z_1,…,z_m):= |(𝒞_1(z_1),…,𝒞_m(z_m))|_⋆.

A monotone norm · on ^N which satisfies (<ref>) for the multi-material cost  is 

    (x_1,…,x_N)= |((x_1,…,x_N_1)^1,…,(x_N-N_m+1,…,x_N)^m)|_⋆.

Observe that the cost associated to the PLC technology corresponds to the choice |·|_⋆ =·_∞ on ^2, _1(z)=λ_1|z|^α_1, and _2(z)=λ_2|z|^α_2.










  (7) Mailing problem. For general m≥ 2 and α>0 consider the following cost

    (z_1,…,z_m):=(∑_i:z_i≥ 0z_i)^α+|∑_i:z_i< 0z_i|^α,

Observe that this multi-material cost does not satisfy (<ref>). A monotone norm · on ^N which satisfies (<ref>) is clearly

    (x_1,…,x_N)=x_+_ℓ^p+x_-_ℓ^p

where p=α^-1 and x_+ (respectively x_-) is obtained by x setting all the negative (respectively positive) coordinates of x equal to zero. Such cost is well-suited to give a better description of the discrete mailing problem (see <cit.>), encoding the fact that, on every branch of a transportation network, there is a gain in the cost of the transportation in grouping particles flowing with the same orientation, but there should be no gain for two groups of particles flowing with opposite orientations.  




 §.§ Examples of calibrations

We now focus on elementary multi-material transportation problems with different costs, for which we are able to exhibit constant calibrations. 



  (1)Mailing problems with Steiner cost. 
Let us consider the multi-material cost :^2→ defined by (x,y)=|x|^0+|y|^0, where we mean that 0^0=0. 

Firstly, we consider the vertices of an isosceles triangle in ^2, for instance p_1:=(ℓ,h), p_2:=(ℓ,-h) and p_3:=(0,0) for some positive numbers h,ℓ with ℓ≥√(3)h, and we fix as a boundary 
    ℬ:=(-1,-1)δ_p_3+ (1,0)δ_p_1 +(0,1)δ_p_2.
 

A solution to the MMTP associated to such boundary and cost is a 1-dimensional integral ^2-current supported on a Y-shaped graph, with angles of 2π/3 between the segments at the junction point (see Figure <ref>). 






In order to translate this into a MMP, we endow ^2 with the norm · which has the unit ball depicted in Figure <ref>. 







In this special case we have to solve a mass-minimization problem for the same boundary ℬ. Now we show that the ^2-valued differential 1-form represented by the matrix

    ω_1:=([     1/2  √(3)/2;     1/2 -√(3)/2 ])
 is a calibration for the minimizer. Indeed 
    ⟨ω_1;(1/2,√(3)/2),(1,0)⟩=⟨ω_1;(1/2,-√(3)/2),(0,1)⟩=⟨ω_1;(1,0),(1,1)⟩=1
 and the form is constant, hence properties (i) and (ii) in Definition <ref> are fulfilled. Moreover, to check (iii), notice that, for every ϕ∈ and every pair of (g_1,g_2)∈^2 with (g_1,g_2)= 1, we have

    |⟨ω_1;(cosϕ,sinϕ),(g_1,g_2)⟩| =|(1/2cosϕ+√(3)/2sinϕ)g_1+(1/2cosϕ-√(3)/2sinϕ)g_2| ≤ 1 ,

where the inequality can be inferred from that fact that the expression in the absolute value is linear in (g_1,g_2) and takes its maximum at some extremal point of the set depicted in Figure <ref>, where the values are ±(1/2cosϕ+√(3)/2sinϕ)=±(sin(π/6+ϕ)), ±(1/2cosϕ-√(3)/2sinϕ)=±(sin(π/6-ϕ)), and ±cosϕ.


Let us now fix as a boundary (supported on the same points) 
    ℬ':=(1,-1)δ_p_3+ (-1,0)δ_p_1 +(0,1)δ_p_2.
 
A minimizer in this case is supported in the union of the two segments joining p_1 to p_3 and p_3 to p_2, respectively (see Figure <ref>).


 




A calibration is the ^2-valued differential 1-form represented by the matrix 

    ω_2:=([ -cosθ -sinθ;  cosθ -sinθ ]) ,
 
where θ is the positive angle between the segment p_3p_1 and the horizontal axis. Again, properties (i) and (ii) of Definition <ref> are verified by construction of this ^2-valued constant 1-form. Moreover, to test (iii), we notice that, for every ϕ∈ and every pair (g_1,g_2)∈^2 with (g_1,g_2)= 1, we have


    |⟨ω_2;(cosϕ,sinϕ),(g_1,g_2)⟩| =|-(cosθcosϕ+sinθsinϕ)g_1+(cosθcosϕ-sinθsinϕ)g_2|≤ 1 ,

again because the expression in the absolute value is linear in (g_1,g_2) and takes its maximum at some extremal point of the set depicted in Figure <ref>, where the values are ±(cosθcosϕ+sinθsinϕ)=±cos(θ-ϕ), ±(cosθcosϕ-sinθsinϕ)=±cos(θ+ϕ), and ± 2sin(θ)sin(ϕ) (observe that sin(θ)≤1/2 due to the choice of h and ℓ).

Lastly, let us consider a boundary datum which is supported on the vertices of a square, say q_1:=(0,1),q_2:=(1,1),q_3:=(1,0),q_4:=(0,0). We set 
    ℬ”:= (0,-1)δ_q_1+(1,0)δ_q_2+(0,1)δ_q_3+(-1,0)δ_q_4.
 A minimizer is given in Figure <ref> and it is supported on the set Σ_1, which is one of the two well-known solutions to the Steiner tree problem for the vertices of the square. This is calibrated by the same ω_1 as in (<ref>), for which all the checks have already been done.




   
Observe also that the other solution Σ_2 to the Steiner tree problem (namely the one obtained from a rotation of Σ_1 by 90^∘) does not support any solution to the MMTP for the boundary ℬ”. Indeed there is only a 1-dimensional integral ^2-current T with ∂ T=ℬ” supported on Σ_2, and by direct computation one can see that this is not a minimizer. Note that T has a vertical stretch (oriented by the vector (0,1)) carrying the multiplicity (-1,1) and we have ⟨ω_1;(0,1),(-1,1)⟩=√(3), hence property (i) of Definition <ref> is not satisfied. Since a calibration always calibrates all the minimizers of the problem, this is another proof that T is not a minimizer.  


  (2)Mailing problems with Gilbert-Steiner cost. Let us consider the multi-material cost :^2→ defined by (x,y)=√(|x|^2+|y|^2). Now consider the boundary datum 

    ℬ:=(N,0)δ_r_1+(0,1)δ_r_2+(-N,-1)δ_r_3,
 where r_1:=(0,1), r_2:=(1,0),r_3:=(-cosθ̃,-sinθ̃), with 

    θ̃:=arccos(1/√(N^2+1)) .
 
Then the Y-shaped graph made by three segments joining at the origin (0,0) supports a solution of the multi-material transport problem (see Figure <ref>).







To prove this, firstly we observe that the associated mass-minimization problem for currents with coefficients in ^N+1 has boundary equal to

    (-1,…,-1,-1)δ_r_3+(1,…,1,0)δ_r_1+(0,…,0,1)δ_r_2,

and a possible norm · on ^N+1 associated to  is 

    (g_1,…,g_N+1)=|(∑_j=1^N|g_j|,g_N+1)|.

Next we check that a constant calibration for such MMP is given by the ^N+1-valued differential 1-form represented by

    ω:=(
    [ 0 1; ⋮ ⋮; 0 1; 1 0 ]) .
 
In fact, (i) holds since

    ⟨ω;(1/√(N^2+1),N/√(N^2+1)),(1…,1,1)⟩=√(N^2+1)=(N,1),


    ⟨ω;(0,1),(1,…,1,0)⟩=N=(N,0)

and

    ⟨ω;(1,0),(0,…,0,1)⟩=1=(0,1).

Property (ii) is satisfied, as usual, because ω is constant. Moreover, for every ϕ∈ and every (g_1,…,g_N+1)∈^N+1 with (g_1,…,g_N+1)= 1 one has

    |⟨ω;(cosϕ,sinϕ),(g_1,…,g_N+1)⟩|≤⟨(|cosϕ|,|sinϕ|);(|g_N+1|,∑_j=1^N |g_j|)⟩,
 and by the definition of ·, the right hand side is the scalar product between two vectors of ^2 having unit Euclidean norm, hence it is bounded by 1.

  (3) For the linear combinations of costs discussed in point (3) of the previous subsection, stepping back to the specific case of <cit.>, we take K=2 and α_1=0, α_2=1. Let us also assume that λ_1+λ_2=1. Hence the single-material cost is (z)=λ_1|z|^0+λ_2|z|. 

We consider the irrigation problem with source of multiplicity 2 in the point p_3 and targets with multiplicity 1 in the points p_1,p_2, where p_1,p_2, and p_3 are as in point (1) of this subsection. As we have already observed, a norm on ^2 which turns this single-material transport problem into a MMP is λ_1·_∞+λ_2·_1. Nevertheless, since we are free to choose any monotone norm which coincides with the above on the positive orthant, then we decide to choose the norm · whose unit ball  is depicted in Figure <ref> (such choice is aimed at reducing the number of extreme points of the unit ball, which makes it easier to estimate the comass norm of the form).






The minimizer for the transportation problem is supported on a Y-shaped graph similar to that shown in point (1), in which the positive angle between the horizontal and the segment joining the branching point to p_1 is θ=arccos((1+λ_2)/2). A calibration, in this case, is represented by

    ω:=
    (
    [           1+λ_2/2  √(1-(1+λ_2/2)^2);           1+λ_2/2 -√(1-(1+λ_2/2)^2) ]) .




To check property (i) of Definition <ref> we observe that

    ⟨ω;(1,0),(1,1)⟩=1+λ_2=λ_1+2λ_2=(2),


    ⟨ω;(cosθ,sinθ),(1,0)⟩=1=λ_1+λ_2=(1),

and

    ⟨ω;(cosθ,-sinθ),(0,1)⟩=1=λ_1+λ_2=(1).

As usual, property (ii) is trivially verified. To check property (iii), we firstly observe that the extreme points of the unit ball for the norm · are ±((1+λ_2)^-1,(1+λ_2)^-1), ±(1,0), and ±(0,1). Now, for every ϕ∈ we have to check that, whenever (g_1,g_2)≤ 1, it holds

    |⟨ω;(cosϕ,sinϕ),(g_1,g_2)⟩| =|(cosθcosϕ+sinθsinϕ)g_1+(cosθcosϕ-sinθsinϕ)g_2|≤ 1 .

We observe that the values of the LHS of such inequality at the extreme points above are respectively given by 2(1+λ_2)^-1|cos(θ)cos(ϕ)|=|cosϕ|, |cosθcosϕ+sinθsinϕ|=|cos(θ-ϕ)|, and |cosθcosϕ-sinθsinϕ|=|cos(θ+ϕ)|. Therefore property (iii) is verified.



To conclude this section, we add a simple, but very useful observation: when the multi-material cost is a composite one (in the sense of point (6) in the previous subsection) but of the form

    (z_1,…,z_m)=_1(z_1)+…+_m(z_m) ,

then the norm |·|_⋆ in ^m is the ℓ^1 norm. Hence roughly speaking, the materials “do not interact”. More precisely, the minimizer is the sum of the individual minimizers of each (single-material) problem associated to the cost _i. This remark matches with the fact that the Monge-type optimal transport of atomic measures is made of “independent” segments joining directly the points at the boundary. Moreover, if one can calibrate with ω_i the problem concerning the i-th material with cost _i, then a calibration of the global problem is a block-diagonal matrix where each block is given by ω_i.














































































































































acm




