Branched Transport

in collaboration with F. Santambrogio



We present on this page some preliminary results on optimal irrigation problems obtained in collaboration with Filippo Santambrogio. We refer to A Modica-Mortola approximation for branched transport and applications for additional details. Such optimal irrigation networks received a large attention last years (see for instance the articles of Xia, Bernot, Maddalena, Morel, Santambrogio and Solimini). Many qualitative results and generalization of the problem have been discussed. Nevertheless, it is surprising that very few has been done on the numerical approximation of optimal networks. One explanation is given by the fact that the exact identification of global optimal networks, in the combinatorial context (see below), is known to be NP hard (with respect to the number of dirac measures).

Two different admissible branched transport

In order to tackle this difficulty we introduced a new continuous framework based on a $\Gamma$-convergence result obtained recently by F. Santambrogio which leads to a very efficient numerical procedure. Let us introduce first this kind of problem in a discrete setting. Consider a compact convex domain $\Omega \subset {\mathbb R}^N $ and two measures which are sum of dirac masses :

\[ s = \sum_{i=1}^m a_i \,\delta_{x_i} \,\, \text{and} \,\, g = \sum_{j=1}^n b_j \, \delta_{y_j} \]

where $(a_i)$ and $(b_j)$ are positive numbers. We ask to $s$ and $g$ to have the same total mass, that is $\sum a_i = \sum b_j$. Following Xia, we define a transport path $(G,w)$ from $s$ to $g$ as both a weighted directed graph $G$ which vertices contains the points $(x_i)$ and $(y_j)$ and a weight function $ w : E(G) \rightarrow {\mathbb R}_+ $ where $E(G)$ is the set of directed edges of $G$. Moreover we ask $w$ to satisfy Kirchhoff's law that is for all vertex $v$ of $G$ we have:

\[ \sum_{e\in E(G),\, e^- = v} w(e)= \sum_{e\in E(G),\, e^+ = v} w(e) + \left\{ \begin{array}{rl} \displaystyle a_i & \text{if $v = x_i$ for some} \; i\\ -b_j & \text{if $v = y_j$ for some} \; j \\ 0 & \text{otherwise} \end{array} \right . \]

where $e^-$ and $e^+$ denote the starting and ending points of each directed edge $e\in E(G)$. To every transport path $(G,w)$ we associate a cost of transportation defined by

\[ M_{\alpha}(G) = \sum_{e\in E(G)} w(e)^\alpha \;\text{length}(e) \]

for some fixed parameter $\alpha \in [0,1] $.

Example of optimal networks and optimal vectorial measures for α = 0.6, 0.75, 0.85, 0.95

We recall below how this discrete problem can be translated in a continuous context and the main $\Gamma$-convergence obtained by F. Santambrogio. Let $(G,w)$ be a transport path associated to the two measures $s$ and $g$. In order to introduce a relaxed formulation to the previous problem we associate to every $(G,w)$ the vectorial measure

\[\displaystyle u_G = \sum_{e \in E(G)} w(e) \, \frac{e^+ - e^-}{||e^+ - e^-||} \mathcal{H}^1_{\vert e}.\]

By definition, the measure $u$ is in the class of vectorial measures of the type $u(M,\theta,\xi) = \theta \xi . \mathcal{H}^1_M$, where $\theta$ and $\xi$ are respectively a positive function and a unit vector field defined on $M$ a set of finite $\mathcal{H}^1$-Hausdorff measure. Moreover Kirchhoff's law in this continuous setting is equivalent to the divergence constraint

\[\nabla . u = g - s.\]

In a analogous way to (costalpha}) we define for every vectorial measure $u$ the cost functional:

\[ M^\alpha (u) = \left\{ \begin{array}{l} \int_M \theta ^\alpha \, d \mathcal{H}^1 \; \text{if $u$ is of the type $u(M,\theta,\xi)$ } \\ + \infty \;\;\text{otherwise} \end{array} \right . \]

Thus, our relaxed optimisation problem is to minimise $M^\alpha$ under the previous (weak) divergence constraint. The $\Gamma$-convergence result we are going to present is based on functionals very similar to the ones of Modica and Mortola but of the form

\[ \displaystyle E_\varepsilon(u) = \varepsilon^{\gamma_1} \int _\Omega | u|^\beta + \varepsilon^{\gamma_2} \int _\Omega |\nabla u|^2\]

defined on $ H^1(\Omega;{\mathbb R}^N)$ with $\gamma_1<0<\gamma_2$. The main difference with Modica and Mortola's functionnal is the fact that the double-well potential has been replaced by a concave power $\beta$ which forces the modulus of the vector field $u$ to tends to $0$ or $+\infty$. The idea is now to choose the parameters $\gamma_1$, $\gamma_2$ and $\beta$ to obtain a functional equivalent (asymptotically when $\varepsilon$ tends to $0$) to the cost (costcont}). Considering that the support of $u$ is concentrated on a segment, an heuristic argument leads to the following choice of the parameters :

\[ \beta = \frac{2-2N + 2 \alpha N}{3-N + \alpha(N-1)},\;\;\frac{\gamma_1}{\gamma_2}=\frac{(N-1)(\alpha-1)}{3-N + \alpha(N-1)} \]

Let us call $M_\varepsilon^\alpha$ the functional associated to a set of parameters satisfying conditions (paramirrig}). F.

${\bf Theorem \,(F. Santambrogio) }$: Suppose $N=2$ and $\alpha \in ]1/2,1[$. Then $M_\varepsilon^\alpha$ $\Gamma$-converges to $cM^\alpha$ with respect to the convergence of measures for some suitable constant $c$ when $\varepsilon$ tends to $0$.

The previous $\Gamma$-convergence result makes it possible to replace an hard discrete problem by a sequence of optimisation problems under linear constraints. In addition, we observed that for $\varepsilon>>1$ the functional $M_\varepsilon^\alpha$ is close from being convex. This observation was the starting point of our optimisation strategy. The main difference between this situation and the previous one is related to the divergence constraint. Due to the very simple structure of the constraints we had to deal with, it was straightforward to compute a projection on the linear constraints in the context.

We present below the first results obtained with our simple approach. The following figures are the results of four different experiments with two different values of the parameter $\alpha$. On the first rows of the figures, we represent two views of the graph of the given density $g-s$. The second rows represent two views of the graph of the norm of the optimal vector field for each value of $\alpha$. As expected, ``Kirchhoff's law is approximatively satisfied'' by the support of the vector field which converges to a one dimensional set. Moreover we observe that two different values of $\alpha$ may lead to very different optimal structures.

Irrigation of a circle with a single source α = 0.6, 0.75, 0.85, 0.95


Irrigation of four targets with two sources α = 0.6, 0.75, 0.85, 0.95


Optimal irrigation of one random configuration α = 0.6, 0.75, 0.85, 0.95