Theory and Approximate Solvers for Branched Optimal Transport with Multiple Sources
Authors: Peter Lippmann
Enrique Fita Sanmartín
Fred A Hamprecht
Venue: NeurIPS 2022 Accept (2022)
Keywords: Combinatorial Optimization
Optimal Transport
Irrigation Networks
Structured Prediction
Steiner Tree Problem
Branched Optimal Transport
Transportation Networks

Abstract: Branched optimal transport (BOT) is a generalization of optimal transport in which transportation costs along an edge are subadditive. This subadditivity models an increase in transport efficiency when shipping mass along the same route, favoring branched transportation networks. We here study the NP-hard optimization of BOT networks connecting a finite number of sources and sinks in $\mathbb{R}^2$. First, we show how to efficiently find the best geometry of a BOT network for many sources and sinks, given a topology. Second, we argue that a topology with more than three edges meeting at a branching point is never optimal. Third, we show that the results obtained for the Euclidean plane generalize directly to optimal transportation networks on two-dimensional Riemannian manifolds. Finally, we present a simple but effective approximate BOT solver combining geometric optimization with a combinatorial optimization of the network topology.

Theory and Approximate Solvers for Branched Optimal Transport with Multiple Sources
Peter Lippmann
Enrique Fita Sanmartin Fred A. Hamprecht
IWR at Heidelberg University, 69120 Heidelberg, Germany (peter. 1ippmannn, enrique. fita. sanmartin, fred. hamprecht) @iwr. uni heriiiheedebbbrrg... de
Abstract
Branched optimal transport (BOT) is generalization of optimal transport in which transportation costs along an edge are subadditive. This subadditivity models an increase transport efficiency when shipping mass along the same route, favoring branched transportation networks. We here study the NP-hard optimization of BOT networks connecting finite number of sources and sinks in R First, we show how to efficiently find the best geometry of BOT network for many sources and sinks, given topology. Second, we argue that a topology with more than three edges meeting at a branching point is never optimal. Third, we show that the results obtained for the Euclidean plane generalize directly to optimal transportation networks on two-dimensional Riemannian manifolds. Finally, we present simple but effective approximate BOT solver combining geometric optimization with a combinatorial optimization of the network topology.
Introduction
23 stipulates transportation costs that increase linearly with the transported mass. However, in many systems of practical and theoretical interest, a diminishing cost property is more realistie: it is more economic to jointly transport two loads with nearby destinations along the same route. The optimal transportation networks under diminishing costs exhibit branching; and indeed, nature and societies are using branched networks, e.g. in blood circulation, gas supply or mail delivery. In this paper, we study the theory and practice of finding good or even optimal solutions in branched optimal transport (BOT).
Optimal transport (OT) 27
More formally, we consider a finite set of sources S with supplies μa >> and sinks T with demands PT 0, located at fixed positions Fg and Tr in IR2 possible transportation network is represented as a directed, edge-weighted graph G(V, EE) with nodes V = S T B. The edges E c V x V interconnect the terminals S and 7 with the help of set of additional nodes B, so-called branching points (BPs), with coordinates TB. The edge direction indicates the direction of mass flow. The edge weights, denoted by me, specify the absolute flows. Gilbert first proposed the BOT problem (9 in which the objective is to solve for
arg min B, B.E.rg.
Σ (
m ||
27ll2 subject to
(1)
supply (
Σ Mis Tik each source 8,
demand Pt
mkk
Myk at each sink t,
conservation Σ mi6 Mije at each BP b,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

0.95
0 0.5
0 Euelidcan Steiner Tree
Optimal Transport
Branched optimal transport (Eq. interpolates between optimal transport and the Euclidean Steiner tree problem. On a toy example, shown are good BOT solutions (found by our approximate solver for * see Sect. (6) for the same set of sources (red) and sinks (blue). The disk sizes indicate the demands and supplies, the edge widths the mass transported along each edge.
Figure I:
given single parameter [0. 1]. The problem of BOT is interesting in that it combines combinatorial optimization (over E) with continuous optimization (over zB. mg).
For 1, the BOT problem is the discrete version of the famous optimal transport problem for which optimal solutions can be found efficiently [6] [23]. However, due to the linearity of the cost function, OT solutions do not exhibit any branching but consist of straight lines between sources and sinks, see Fig. la In contrast, for a E [0, 1). the subadditivity of m + m reflects the increased efficiency of transporting loads together, i.e. (m² + -m22 < =mf m2. Thus, for [0, 1), BOT solutions show branched structure, see Fig. Tb d Unlike OT, the optimization problem of BOT NP-hard [T]. In the special case of tree problem (ESTP) (28 13]. In the ESTP, the objective is to find the overall shortest network that interconnects all terminals (with the help of BPs), independently the edge flows, since m For different values of a, BOT interpolates between these two optimization problems, see Fig.
BOT turns into the well-studied Euclidean Steiner
Connection of BOT to machine learning. Optimal transport has emerged important tool in machine learning [ 3 23 BOT a strict generalization, describing a more versatile concept and more challenging optimization problem.
BOT offers a mathematical formalism that deceivingly simple (cf. Eq. TT) and yet engenders non-trivial structure. Many machine learning problems such as tracking of divisible targets (computer vision), skeletonization (image analysis), trajectory inference (bioinformatics) come with input that essentially continuous (images, distributions) and require structured output that is discrete, e.g. graphs. Arguably, this transition from continuous to discrete is one the most interesting aspects (and an unsolved problem) in current machine learning research. It is also problem that cannot be solved by a mere upscaling of standard deep learning architectures.
In addition, routing problems have become popular problem to challenge machine learning and amortized optimization algorithms with difficult optimization problems [17 B [5].
Combining
combinatorial and continuous optimization, BOT is highly instructive target for new machine learning approaches. In Sect. 7 we address the generalization of BOT higher-dimensional Fuclidean space, particularly relevant for applications in data science.
In this paper, we make the following contributions: We generalize an existing method for constructing BOT solutions with optimal geometry the case of multiple sources. Based on this generalization, we present analytical and numerical scheme to rule out n-degree branchings with n > 3. Further, we demonstrate how to extend geometric and topological properties of optimal BOT solutions to two-dimensional Riemannian manifolds. Lastly, we propose more practical numerical algorithm the geometry optimization together with a simple but compelling heuristic, addressing the readily accessible code for
optimization of the BOT topology. To the best of our knowledge, finding BOT solutions is publicly available. By making our code available at /gchhii-aa unwnd/ wathh///raaneurrrree we hope to aid the evolution of the field.

---

2 Topology and geometry of BOT solutions
BOT problem can be divided into the combinatorial optimization of the network topology, specified by the set of BPs B and edges E' (see Sect. [ and the geometric optimization of the BP positions 2 Bernot et al. [2] showed that optimal BOT solutions can be assumed to be acyclic, which restricts the search for the optimal topology to trees. Given n terminals, WLOG, the topology can be represented BPs, each of degree three. Higher-degree branchings may effectively form during the geometry optimization if multiple BPs settle at the same position. A set of such BPs is referred to as coupled BP, cf. Fig. [2 The union set of all neighbors of the individual BPs (not including the BPs themselves) is referred to as set of effective neighbors. Conversely, BP configuration which all BPs are uncoupled and located away from the terminals called non-degenerate, see Fig. 2a
as so-called full tree topology, which has
The number of distinct full tree topologies interconnecting n terminals given by (2n-5)1 -
(2n-5)- (2n -.. -3-1 and hence increases super-expomentiall with the number of terminals (25] Given 100 terminals, one would have to consider more than 10 possible full tree topologies, making an exhaustive search computationally intractable already for problems of modest size. Fortunately, given a tree topology, the geometric optimization of the BP positions reduces to convex optimization problem, as all edge flows myj are already uniquely determined by the flow constraints in Eq. (I) The corresponding linear system can be solved in linear time by dynamic programming. called "elimination on leaves of a tree" in [26]. Since the Euclidean norm, like any norm, is convex, given a fixed tree topology, the cost function Eq. (T) becomes a convex function of the BP positions. Together with the independence of the individual BPs, this implies the following lemma on the optimal substructure of BOT solutions (see App. C).
Definition 2.1. For a chosen topology T. BOT solution is called relatively optimal solution (ROS of T) if its BP configuration has minimal cost. The overall best BOT solution, given by the optimal topology together with its ROS, is called the glob- ally optimal solution (GOS).
(B,.b.)
(a) Non-degenerate BP configuration
(b) Coupled BP with effective degree
Lemma 2.1. (a) For given free topology. a BOT solution is relatively optimal if and only if every (coupled) BP connects its (effective) neighbors at minimal cost. (b) In a globally optimal solution, every subsolution restricted to connected subset of nodes solves its respective subproblem (cf. App. C) globally optimally.
Figure 2: Two BP configurations for the same full tree topology: A higher-degree branching may effectively form by coupling the two BPs at the same position.
3 Geometric optimization of BOT solutions
Although the BP optimization for a given tree topology is a convex problem, as argued above, is non-trivial, since the objective function is not everywhere differentiable. Here, we present a principled geometric approach, which was first suggested by Gilbert in [9] and previously developed in the context of the ESTP (00.. More recently, this approach was discussed in the comprehensive work by Bernot et al. (2). where it was applied exclusively to BOT problems with single source. A generalization the case of multiple sources was posed an open problem by the authors (see Problem 15. for which we give the solution in this section.
3.1 Geometric solution for one source and two sinks
Motivated by Lem. 2.1 start by considering single BP b in isolation (cf. Fig, 3ap. following 22] Given a source at position ag and two sinks at positions aj and a2, we aim to find the optimal position 6* for the BP connecting the three terminals, i.e., the minimizer of
C(b) mf
m2 a2 b| + (m, + m22) (ag - 6),
where my and m2 are the respective demands of the two sinks. Due to the convexity of C(b), the minimum must lie either stationary point at which V, 0 at a non-differentiable point,
We will often use the node label, e.g.. ao, denote also the position of the node, instead of writing Tap-
3

---

20
20
191
mm m1
(a)
(b)
(c)
(d)
Figure 3: (a) Branching point b connecting source and two sinks with branching angles 01 and 0g. (b) Construction of the optimal BP D" applying twice the central angle property illustrated in (c).
(d) shows the relation of the optimal branching angles 0 and 07, relevant for the case of asymmetric branchings (see Sect. 3.2)
where b coincides with one of the a; Bernot et al. showed that the gradient is equal to zero if and only if the branching angles Oi see Fig. 3a are given by
2,2 - (1 - 2:)20
0- arccos
=: f(a,a,,, k:),
2k
(1 - 22 22
0 arccos
=
2(1-
- k.a0 (1 -k)2aa =(a
0 0 arccos
2k (1 k))
where we have defined the flow fraction == m1/(m, + m2) and the two functions f and h, related
via h(a, k) = f(a, k)) + f k). If BP exists that realizes the branching angles ff, it can be constructed geometrically based on the central angle property (see App. A). states that, given a circle through @1 and (22, the angle /a, 002 the center is twice the angle enclosed with a point anywhere on the opposite circle arc, cf. Fig. 3c In particular, let us construct the so-called pivor circle with central angle Za1 00g 20 20 and pivor point p as in Fig. 3b Applying the central angle property twice (once for 01 and once for 02), a BP located at the intersection of the lower circle are and the connection line aop realizes both angles 0; and is therefore optimal.
However, given the pivot point and pivot circle, agp may not intersect the lower circle arc, depending on the position of ag. Accordingly, the lower half plane be partitioned into region for which the described construction yields an optimal Y-shaped branching and three other regions, see Fig. 5 For ag located in one of these regions, the optimal BP position coincides with one of the terminals. resulting in a V-shaped branching (b* = og) or an L-shaped branching (b* E {ai, (2 cf. Fig. 11
3.2 Geometric construction of BOT solutions for given topology
Applying the geometric construction from above in recursive manner, one can construct the ROS (see Def. [ef. for larger BOT problems, as illustrated in Fig. Given a full tree topology T. first, we determine all edge flows (see Sect. ( and consequently the optimal branching angles. Then, root node is chosen, arbitrarily (here ao), and other nodes are sorted based on the number of edges to (ignoring edge directions and resolving ties arbitrarily). Starting from the furthest nodes and working towards the root, two nodes are recursively summarized by pivot point, constructed from the optimal branching angles, iteratively, each as in the 1-to-2 case, see Fig. realized at every BP and the resulting solution
Fig. 4a b Afterwards, in reversed order, the optimal BPs placed 4 d In this manner, the optimal branching angles are ROS of T by Lem. 2.
The choice of the root node induces a node ordering as described above. Given this ordering, consider any BP b and denote its children by a1 and d2 and its parent node by The construction of the pivot point now requires the positions a and d2 and the optimal branching angles enclosed by the children edges (b, an) and (b, az). However, the branching angles do not only depend on the absolute flows my and m2 of the respective edges but also on the flow directions. Given that both flows point towards b or given that both flows point away from b, as in Fig. 3al the branching is referred to as

---

(b)
(c)
(d)
Figure 4: Recursive geometric construction relatively optimal solution, using one pivot point and pivot circle per branching point to collectively realize the optimal branching angles.
symmetric and the optimal branching angles of interest are given by 87. cf. Eq. (3). Note that BOT problems and their solutions are fully symmetric under complete exchange of sinks and sources (up to reversal of all flow directions). On the contrary, in case of one flow pointing towards and one pointing away from b, referred to as asymmetric branching, the optimal branching angles 07 enclosed by the children edges are calculated differently, Fig. 3d] However, the branching angles of can be related geometrically to the known 87. Using the functions f and h from Eq. (3) we find that
0 π 0 0% = h a=
m2 m1
m2
83 0 f( f(a, m2 m1
m2
After determining the angles of and 0h from the flows my and m2, the BP construction based on the central angle property works analogously to the symmetric case. Crucially, this distinction of symmetric and asymmetric branching makes the recursive construction applicable also problems with multiple sources, where asymmetric branchings may be unavoidable, consider c.g. Fig. 4d with ao and 0z as sources and 01 and a2 as sinks (see App. G.1). Further, note that the known conditions for optimal V- and L-branching can be transferred to the asymmetric case simply by relabelling ag - d2. 01 - ag and 02 > a1, cf. Fig. Ba and Fig. 3d In terms of angular inequalities (derived in App. B), these conditions, for both branching types, are summarized in Table
symmetric branching
asymmetric branching
Zaz 0g02 2 0 + 02
1.2: Zagazai 2 0f + 02
LI: Zazajag 2 π 02
V: Lajagaz 2 π
12: Zagaga1 2 0f
L1: Zazarao Of
Figure 5: Regions of optimal Y-, V- and L-branching.
Table Relations between the L- and V-branching condi- tions.
In principle, given full topology. the described method efficiently constructs the ROS in linear time. However, as already pointed out by Gilbert [9], the approach has some practical limitations, after our generalization. Figure 3b shows how the pivot point is constructed only from the positions of two children aj and ag and the corresponding optimal branching angles. However, a priori there are two possible pivot point locations, one in the upper and one in the lower half plane with respect to 02 Hence, the construction relies on knowing in which half plane the third node ag lies. For larger trees, the topological parent 0g may itself be BP whose position is yet determined. In the worst case, one would thus have to try all 2 possible pivot point combinations find the ROS. This pivot point degeneracy gets substantially worse higher dimensions, making the recursive construction applicable only in IR?. Secondly, the geometric construction only produces solutions which are non-degenerate, i.e., solutions without edge contractions. construction is therefore primarily of theoretical interest; and indeed, it forms the basis of our following arguments. Note that both the aforementioned problems could be solved elegantly the special case of a 0 [12 [4]
now, the geometric
5

---

4 Properties of optimal BOT topologies
Let us now consider topologiaal modifications in order to improve the transportation cost of BOT solution. In particular, we intend to show that a topology T can be improved if its ROS contains coupled BPs. Let us start by considering a general BOT solution which contains coupled 4-BP, i... a coupled BP with four effective neighbors, as in Fig. 2bb Lemma 2. states that a solution is not globally optimal if any subsolution is not globally optimal. It will therefore suffice study the coupled BP as an isolated subproblem.
4.1 Non-optimality of coupled branching points
Given two sources and two sinks, there are two possible configurations in which the terminals can be arranged, cf. Fig. ba b the terminal quadrilateral, as in Fig. 6al Based on Lem. 2.1 a necessary condition for the existence of globally optimal 4-BP is that all four V-branchings between neighboring terminals are optimal. This puts lower bound on each of the angles "i see Tab. [ The general idea, also regarding the other b-banchhng scenarios, is to show that the angular sum of these lower bounds already exceeds 2T. This will immediately imply that not all V-branchings can be optimal simultaneously and thus a coupled 4-BP cannot be globally optimal. Given 4-BP as Fig. 6a all V-branchings are asymmetric (i.e. neighboring flows point in opposite directions). Hence, all four lower bounds (in Tab. [ are of the form 7; 2 π - 0 = π s(a,) k) and indeed π f(a k) > x /2, see Lem. D.I, so that their sum exceeds 2m.
First we address the case which the two sources are at opposite corners of
Next, let consider the scenario in Fig. 6b with two sources at neighboring corners WLOG, we use the normalization my m2 1 m3+m1
M
and assume that my > my and m2 < m4. In this case, the four conditions for optimal V-branching in Tab. T read:
71 2 π - a(
ms = 1( 1(a, ax my
mi
(a)
(b)
(c)
72 2 h ((a mi mm = m(a,,.))
mi
Figure 6: Different scenarios of coupled 4-BPs with symmetric branching angles in blue, asym- metric ones in orange.
73 2 -- 1 (a, 1- my m2
1- mm - 1-(1 ((a
1-m3)
m4
74 1//2 h
a.
+y+
mi
= ma).
where the expressions were plugged into the V-branching conditions in Tab. I for symmetric and asymmetric branching respectively, as indicated by the colors in Fig. ( Let us show that in fact for all combinations of a, my and my the sum of the lower bounds already exceeds 2T. Indeed, summing the lower bounds and subtracting 2 yields
Mm1) + -((m))) -
M3
mi
h(1 - mm) + M(ma)) - [(ma) f(1 - -m1)
m
m3
=k(1-m1)
>> mg
> mm
= =f(m1) + f(1 - -m3) > O. using h(a, k) f(a, k) + f(a, 1 k) and the fact that fa, k) is strictly decreasing with respect to k, see Lem. D.1. To summarize, we have arrived at the following lemma:
Lemma 4.1. A coupled 4-BP not coincident with terminal connecting two sources and two sinks is never globally optimal.
Exactly the same logic applies for coupled 4-BP connecting one source and three sinks (or equivalently 3 sources and sink), as in Fig. 6c WLOG, in the following, we normalize the flows so that mi + m2 + m3 = We then determine the necessary conditions under which all V-branchings are optimal. We again intend to show that such a 4-BP can never be globally optimal by showing that for any combination of a and m, the sum of the lower bounds exceeds 2x. This is equivalent to proving the following inequality (see App. 1.1.1):
h
m1
f(1 + h
m3
fmm)) 0.
m1 + m2
my + m22

---

Assuming a globally optimal 4-BP existed, one could continuously displace a terminal in a way such that for the resulting BOT problem coupled 4-BP still globally optimal. Choosing different such displacements four additional inequalities can be derived (see App. F.
Proposition 4.2. Given BOT problem with one source and three sinks, with demands m1, m2, mg as in Fig. 6c a coupled 4-BP away from the terminals cannot be globally optimal if at least one of the following inequalities holds true:
r = 1
m1
[(m)) +
m3 + m2 ) [(m3) > 0,
Mg
+ m2
) 5(1-
- 1-m, m, ) - -f(11 m. m2) > 0,
m2
11,- = f(1 ([.m)))=
22 h( ( m ) + 1 1 m,
m2
-h(m²) > 0
(m. m,, + m2
where * 1,3. Note that p= 11, + T22 T1.3 + T223-
In App. 1.1.3, we prove the inequalities analytically for a large subset of the parameter space. For the remainder we present a numerical argument (see App. 1.1.4). In addition, we show by induction how, given that coupled 4-BPs are never globally optimal, one can further rule out coupled n- R-BPs (with effective neighbors) for all n 4.
Theorem 4.3. Given a BOT problem in the Euclidean plane and assuming that coupled 4-BPs are never globally optimal, in a globally optimal BOT solution each branching point not coincident with a terminal must have degree three.
Generalization of BOT to Riemannian manifolds
In this section, we extend the BOT problem together with many of the previous results to two- dimensional Riemannian manifolds M embedded into R$ [18] This includes the sphere as important special case, particularly relevant for global transportation networks. In the generalized BOT cost function (5) replace the Euclidean metric by the geodesic distance d M x M + i,i..
Cms Σ mi 2;). (UJE
(5)
As we assume the manifold to be embedded, the length of geodesics can be measured in R3 First, we generalize the non-optimality of cyclic solutions. The corresponding proof in (2) readily applies also two- and higher-dimensional manifolds. As before, solving BOT problem on curved surface can thus be separated into the combinatorial topology optimization and the continuous optimization of the BP configuration.
5.1 Linear approximation of BOT solutions manifolds
Intuitively speaking, a two-dimensional Riemannian manifold locally looks like the Euclidean plane. If we zoom in sufficiently small region, geodesics again resemble straight lines and the geodesic distance approaches the Euclidean one. This can be used to show that the branching angles which were optimal for Y-branchings in the Buclidean plane are also optimal on Riemannian manifolds. Below, we summarize the main steps of the proof. All details can be found in App. F.
Given Y-branching on a manifold, we measure the angles between the three geodesics in the tangent space TrM at the BP b. We now zoom in on a small neighborhood U around b and consider only the subsolution in M N. The terminals of the corresponding subproblem are projected orthogonally onto the tangent space, more specifically onto a small disk of radius r, denoted by (rr), see Fig. 7 Let us denote the cost of the subsolution the manifold by Cas (b) and the cost of the corresponding subproblem in the flat disk by C(b). Now, assuming that the angles between the geodesics deviate from the optimal branching angles, the same holds true for the projected subsolution. Consequently, there exists an alternative BP b' in the disk with cheaper cost C(b"). Note that the radius of this disk becomes smaller the smaller we choose the region M of the subproblem.
7

---

Crucially, the cost difference between a subsolution on the manifold and its projection onto the plane tends zero quadratically in the limit of r + 0. The intuitive reason for this that the tangent space T&M locally approximates the manifold to linear order. On the contrary, the costs C(b) and C(6") in the disk scale linearly in r and so does the cost improvement (b) C(b*) M r. for some fixed M >> O. To conclude the proof, one projects b* onto the manifold and evaluates the cost difference of the two subsolutions there. The difference is of the form M r r (rr), with second order differences due to the projection from D(r) to the manifold. Consequently, a finite radius r > O must exist for which the
T.M
Figure 7: On the flat disk D(r) C TT,, the BP does not solve the problem with terminals â optimally the angles between the dotted geodesics are not optimal.
the cost difference is truly positive. A BOT solution manifold for which the Y-branching angles deviate from the optimal branching angles can thus be improved and is not relatively optimal. The logic of the proof outlined here can easily be extended the V- and L-branching conditions as well as our results regarding the non-optimality of coupled BPs. Again, improving the BOT solution locally in the tangent plane (w...t its geometry or topology) and projecting back to the manifold results in an improved solution on the manifold (see App. F.2).
Theorem 5.1.
Consider the solution to a generalized BOT problem on a two-dimensional Riemannian manifold embedded into R². For the solution be relatively optimal, it is necessary condition that each BP satisfies the optimal angle conditions for Y-, V- and L- L-branching, which apply for BOT in the Fuclidean plane. For be globally optimal, assuming that coupled 4-BPs not optimal in the plane, it is a necessary condition that BPs not coincident with a terminal have degree three.
Though there is readily available algorithm to solve BOT on embedded surfaces, we discuss some possible approaches in App. F.3.
Heuristics and numerical optimization
In this section, we present simple but effective algorithm for the geometry optimization, followed by a compelling heuristic for the topology optimization. As pointed out carlier, the difficulty of solving BOT problem stems from the super-exponentially growing number of possible full tree topologies. Obtaining an exact solution by brute-force is almost always computationally infeasible and hence fast heuristic solvers are needed. For BOT problems with single source, branch-and-bone method is applicable [31), enabling exact solutions for up to 16 nodes. However, this method does not generalize directly to the case multiple sources. While some literature exists on heuristics for BOT problems with single source [29]. we are not aware of heuristics for multiple sources, except 24 The authors of (24) present a simulated annealing based optimization strategy for BOT, supervision. based on continuous approaches to solve BOT exist which do not rely on a subdivision into Furthermore,
geometrical and topological modifications, which may require
geometry and topology optimization. The authors of (22) phrase BOT a limit of functional minimization problems. Since their algorithm discretizes the plane and the BOT cost function, their output is however not sparse but discretized function.
6.1 Numerical branching point optimization for given topology
Brute-force and heuristic BOT solvers alike typically rely on the geometry optimization of many different topologies. A fast and reliable BP optimization routine is therefore essential, as it determines the computational bottleneck of these algorithms. For a given tree topology T, all edge flows my are known (see Sect. 2 The objective is thus to minimize the following convex cost function:
c((r,))
Σ (GJ)
m || - 1.y12
where, for 1 < i S n. the 2; hold the fixed coordinates of the terminals and, for n + < S n m, the variable BP positions. Since the cost function is not everywhere differentiable, we suggest the following generalization of Smith's 'ss algorithm developed for geometry optimization in the ESTP (26).
8

---

It is an effective algorithm specifically for minimizing the sum of Euclidean norms in two- and higher-dimensional Euclidean space. Unlike the geometric construction in Section 3.2 it applicable to all (not necessarily full) tree topologies.
Starting from non-optimal, non-degenerate BP configuration, e.g- from random initialization, the gradient with respect to each BP position x; is set to zero for n + 1 < i S n + m, resulting in the following non-linear system of m equations:
a 3; Tz
Σ
Σ
Fi
Tij
5: (JJ)TT
(:(j-)
This system can be solved approximately, by iteratively solving the following linearized system
(b+1)
(k+1) T
mi (k)
(8)
Σ
(k) 1 - 01
m
for n + +igisnn m. (7)
(:(1))
J J:(HJE
Note that x; (k) Ij is fixed for S S n. For each iteration, the solution can be found in linear time, again by "climination on leaves of tree", similar to determining all edge flows from the flow constraints. The algorithm is easily parallelized over d spatial dimensions of BOT problem so that single iteration is of order ((n)). In essence, this is an iteratively reweighted least squares (IRLS) approach [4. The connection is made explicit in App. G.2. Details on the proof of convergence. the empirical runtime of the algorithm and suitable convergence criteria can be found in App. G.2 and in [26]. The arguments in [26) readily apply to our generalization. Besides our method, other techniques may be used for the geometry optimization, for instance the interior point method presented 130
6.2 A greedy randomized algorithm for the topology optimization
Our heuristic for the optimization of the BOT topology is inspired by the idea of simulated annealing [6].. which has been applied in different variants to combinatorial problems such as the Traveling Salesman Problem [19]
1.10
sample
mcan
or the ESTP [10]. In our heuristic, the BOT topology is iteratively modified by randomly deleting an edge and
sverage codt rati
replacing it with a new one. At each step, the new solu- tion is accepted according to a criterion, which typically depends on the cost difference between the solutions and a user-chosen hyperparameter, the temperature, used to mimic a physical cooling process. However, because in practice it works already sufficiently well (see Fig. we refrained from designing elaborate cooling scheme. Instead, we apply the heuristic most greedily, i.c., the cero-temperature limit, where new state is accepted only if decreases the cost.
1.04
1.02-
1.00
9
number of terminals
Figure 8: Cost ratios our greedy heuris- tic and prute-force solutions (the closer to the better) for different number of termi- nals n. For each 100 different BOT problems. Most runs ended up close to the global optimum (see dark blue assembly near 1.0).
Starting from an initial tree topology T. e.g., the mini- mum spanning tree (mST) or the OT solution we uni- formly sample edge é E E and remove it from T. Let the incident node of é which ended up the smaller connected component be L. Then, one calculates the distance d(e, E) between É and every edge = (i.j) in the larger component and samples one of these edges with probability p(e) x exp(-d(e, e)2/d /d where dmni is the distance to the closest considered edge. The node is then connected to the sampled edge via new BP produce new tree topology. For this topology. we optimize the geometry (as described in Sect. [.1 and compare costs with the previous solution. If the new state rejected, start the next iteration by sampling è without replacement until either move is accepted and all above steps are repeated; or until no accepted move is found, upon which the search terminates.
uniformly sampled
In particular in the regime z 1, our BOT solver benefits from existing efficient OT solvers by using their solution initial guess.

---

Experiments for small BOT problems suggest that even in the greedy ero-teemeerature limit the algorithm often finds the globally optimal solution, after comparatively few iterations. For this, the greedy heuristic (using the mST as initialization) was compared against exact solutions with up to nine terminals, obtained by brute-force. For each ni 100 BOT problems were sampled uniformly with respect to the terminal positions and demands and supplies, ef. Alg. 2. The ratios of the heuristic's cost divided by the cost of the exact solution are plotted Fig. g On average the heuristic solution is less than 0.5% worse than the brute-force solution. This is impressive, considering the fact that for n = 9 the brute-force solver requires over 10 BP optimizations, whereas the simulated annealing heuristic on average required 29 = 10 iterations converge. Additional experiments (also for larger BOT problems) suggest that the number of BP optimizations until convergence scales better than (n ) see App. G.3. Further, the cost ratios in Fig. 8 stay roughly constant as n increases. Additional experiments for BOT in higher dimensions (see Fig. 28) indicate that the average quality of the heuristic solution decreases only very slightly with n. Unfortunately, one can only speculate how this trend extends to larger BOT problems, where brute-force solutions are no longer feasible. Figure T shows heuristic solutions of a larger example problem for different values of In particular, find that the greedy heuristic is very effective at removing higher-degree branchings and undesirable edge crossings.
7 Generalization to higher-dimeensioall BOT
Optimal BOT solutions are acyclic also in Rd 2 Thus, for a given topology, the edge flows are known, the optimal substructure property of Lemma 2.1 generralzs and the convex geometry optimization can be separated from the combinatorial topology optimization. Though, the optimal angle conditions for Y-, V- and L-branching (see Sect. 3) hold also in IR the results on the degree limitation do not generalize, as the arguments rely on the fact that the angles between edges meeting at a higher-degres branching point sum up to 2nT (cf. Sect. (4.)). The numerical geometry optimization as well as the greedy algorithm for the topology optimization presented in Sect. ara readily applicable to BOT problems in R2 (see also App. G.2 and App. G.3).
8 Conclusions
We have studied branched optimal transport in IR2 from a theoretical and practical perspective. First, we have tackled the geometric optimization of BOT solutions, given a tree topology. We generalized the existing exact method presented in 22 D the case of multiple sources. Based on theory developed in the process of this generalization, we formulated a catalog of necessary and sufficient conditions for optimal BOT solutions and argued that n-degree branching points for n > are never optimal. Moreover, we showed that these conditions also apply for BOT on two-dimensions manifolds. Lastly, we presented a greedy randomized algorithm, which optimizes the tree topology. combined with an efficient numerical branching point optimization method. We compared our algorithm to the optimal solution for small examples, obtaining compelling results.
BOT provides a unifying framework for optimal transport and the Euclidean Steiner tree problem and is itself of great theoretical and practical interest. The emergent branching in BOT can be used to simulate and study the myriad of efficient transportation systems which exhibit subadditive costs. Moreover, BOT combines both combinatorial and convex optimization and could be an inspiring problem to be solved by machine learning techniques. The number of optimality criteria derived in this paper can guide further research in this area and the presented approximate solvers may serve as competitive baseline for new ML-based approaches.
Acknowledgments and Disclosure of Funding
We would like to thank Jaroslaw Piersa for sharing his code with us for a comparison to his work. Further, we thank Edouard Oudet for helpful hints on the comparison to his related work and Fabian Egersdoerfer for his improved C++ implementation of the geometry optimization.
This work is supported by Deutsche Forschungseemeinschatt (DFG) under Germany's Excellence Strategy EXC-2181/1 390900948 (the Heidelberg STRUCTURES Excellence Cluster), by Infor- matics for Life and by SIMPLAIX funded by the Klaus Tschira Foundation.
10

---

References
[1] M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein generative adversarial networks. In International conference machine learning, pages 214-223. PMLR, 2017.
[2] M. Bernot, Caselles, and J.-M. Morel. Optimal transportation networks: models and theory. Springer, 2008.
[3] Q. Cappart, D. Chételat, E. Khalil, A. Lodi, C. Morris, and P. Veličković. Combinatorial optimization and reasoning with graph neural networks. arXiv preprint arXiv:2102.09544, 2021.
[4] R. Chartrand and W. Yin. Iteratively reweighted algorithms for compressive sensing. In 2008 IEEE international conference acoustics, speech and signal processing, pages 3869-3872. IEEE, 2008.
[5] N. Courty, R. Flamary, D. Tuia, and A. Rakotomamonjy. Optimal transport for domain adaptation. IEEE transactions on pattern analysis and machine intelligence, 3959):1833-1865, 2016.
[6] M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26:2292-2300, 2013.
[7] J. Dolan, R. Weiss, and J. M. Smith. Minimal length tree networks on the unit sphere. Annals of Operations Research, 33(7)5501-535, 1991.
[8] P. T. Fletcher, S. Venkatasubramanian, and S. Joshi. Robust statistics on Riemannian mani- folds via the geometric median. In 2008 IEEE Conference on Computer Vision and Pattern Recognition, pages 1-8. IEEE, 2008.
[9] E. Gilbert. Minimum cost communication networks. Bell System Technical Journal, 46(9): 2209-2227, 1967.
[10] G. R. Grimwood. The Euclidean Steiner tree problem: Simulated annealing and other heuristics. 1994.
[11] G. M. Guisewite and P. M. Pardalos. Algorithms for the single-source uncapacitated minimum concave-cost network flow problem. Journal of Global Optimization, 1(3):245-265, 1991.
[12] Hwang. linear time algorithm for full Steiner trees. Operations Research Letters, 4(5): 235-237, 1986.
[13] K. Hwang and S. Richards. Steiner tree problems. Networks, 22(1):55-89) 1992.
[14] K. Hwang and Weng. The shortest network under a given topology. Journal of Algorithms, 13(3):468 488, 1992.
[15] C. K. Joshi, T. Laurent, and Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint MXXiv/99660/222 2019.
[16] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. science, 22014598):671-6680 1983.
[17] W. Kool, H. Van Hoof, and M. Welling. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08477 2018
[18] J. M. Lee. Introduction to Riemannian manifolds. Springer, 2018
[19] M. Malek, M. Guruswamy, M. Pandya, and H. Owens. Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem. Annals of Operations Research, 21(1):59-88 84, 1989.
[20] A. Melzak. On the problem of Steiner. Canadian Mathematical Bulletin, 4(2):143-148, 1961.

---

[21] B. Mordukhovich and N. M. Nam. The the light of convex analysis. arXiv preprint arXiv: 2013.
problem and weiszfeld's algorithm in
[22] E. Oudet and Santambrogio. A Modica-Mortola approximation for branched transport and applications. Archive for rational mechanics and analysis, 201(1):155-142 2011.
[23] G. Peyré, M. Cuturi, al. Computational optimal transport: With applications data science. Foundations and Trends in Machine Learning, 11(5-6):355-607 2019.
[24] J. Piersa. Ramification algorithm for transporting routes in r2. In 2014 IEEE 26th International Conference on Tools with Artificial Intelligence, pages 657-664. IEEE, 2014.
[25] E. Schröder. Vier combinatorische probleme. Z. Math. Phys, 15:361-376, 1870.
[26] W. D. Smith. How to find Steiner minimal trees euclidean d-space. Algorithmica, 7(1):
137-177, 1992.
[27] C. Villani. Optimal transport: old and new, volume 338. Springer, 2009.
[28] D. M. Warme, Winter, and M. Zachariasen. Exact algorithms for plane Steiner tree problems: computational study. In Advances in Steiner trees, pages 81-116. Springer, 2000.
[29] Q. Xia. Numerical simulation of optimal transport paths. In 2010 Second International Conference on Computer Modeling and Simulation, volume pages 521-525. IEEE, 2010.
[30] G. Xue and Ye. An efficient algorithm for minimizing a sum of Euclidean norms with applications. SIAM Journal Optimization, 7(4):1017-1036, 1997.
[31] G. Xue, T. P. Lillys, and D. E. Dougherty. Computing the minimum cost pipe network interconnecting one sink and many sources. SIAM Journal on Optimization, 10(1):22-42, 1999.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] see Sect. 3.2
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] see e.g. Fig. 23
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See App. G
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "pLi6wTF0b0S", "reviewer": "Reviewer_mpG7", "summary": "The paper under review studied the problem of branched optimal transport with multiple sources.\nAs a generalization of OT, BOT optimizes the transportation by allowing extra branching points. \nA hyperparameter $\\alpha$ is used to control the efficiency of transporting mass together.\nThe transportation flow is captured as a graph, whose vertex set contains the sources, sinks and BP.\nIn order to obtain an optimal solution, \none needs to find both how vertices are connected (topology) and where the BPs are located (geometry).\n\nUnder the above framework, the authors proved that for a graph to be optimal, \nthe degree of a branch point has to be 3. \nMoreover, the authors provided an analytic approach and a numerical algorithm to find the optimal locations of BP.\nFurthermore, the authors presented an algorithm to approximate the optimal topology of BOT.\nIn addition, the authors considered generalization to 2-D Riemannian manifolds.\n", "questions": "Q1: Regarding the topology of $T$: it is unclear what information are enclosed in the topology of $T$.\nFrom the description in the paper, it seems only the graph structure is consider as the topology of a tree.\nHowever from the set up (eq 1), number of branch points ($|B|$), weights on edges ($m_{ij}$) are all variables.\nHow does one optimize these. In particular, for instance if two edges going out of a source, how does one \ndetermine how much flow each edge shall carry? \n\n\n\nQ2: (continuation of Q1) In line 106, the authors stated \"first, we determine all edge flows (see Sect. 2)\".\nHow are the edge flows are chosen? Could not find in section 2. Are the edge flows randomly initialized, \nthen optimized somehow?\n\n\nQ3: Line 289: \"Then, one calculates the distance $d(e, c)$\nbetween $c$ and every edge $e = (i, j)$ in the larger component\". How does the distance $d(e, c)$ is defined here?\n\nQ4: Some interpretation on \"no degree greater than 3 branch points \nare possible for optimal solution\" would be nice.\nIf it is just graph, one can easily switch between\na degree 4 branch point and two degree 3 branch points.\nIt is not feasible when cost are related,why?\n\nQ5: Is the optimal solution for BOT unique? \n\n\n\nMinor points: \n- change of disk sizes in Fig 1 is not that visible, could scale a bit more.\n\n- it is probably better to move algorithms to the main text if space allows.\n\n- line 293, \"node c\" --> \"component c\".\n", "limitations": "The authors mentioned that it is difficulty \nto verify the efficiency of the proposed algorithm for large BOT problem. \nMy guess is that the running time will be long for the proposed BOT problem comparing to OT.\nConsidering BOT is a NP-problem, it is expected. It would be nice if the authors could say a bit \nmore along this line.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper is well-written and easy to follow.\nThe idea of allowing multiple sources for BOT is natural, \nthe interpolation between OT and euclidean Steiner tree problem is interesting. \nThe results are novel and sound.\n\n\nWeaknesses:\n\nA little concern regarding the motivation and practicality.\n\nMotivation: it would be nice if the authors could provide some further explanation why would BOT be useful.\nFor example, describe a practical example where combined transportation is feasible,\nthen in that example, how do one pick $\\alpha$ to model the case (illustrate that OT is not optimal).\nAnd further how to use algorithms (or theoretical results) developed in this paper to obtain an optimal plan.\n\nPracticality: the running time is not shown in the paper, how fast is the algorithm comparing to Sinkhorn for OT,\ni.e. for a given problem, pick $\\alpha = 1$, $\\alpha = 0.5$, run Sinkhorn for $\\alpha = 1$, \nrun Alg 1 and Alg3 (from the supp) for $\\alpha = 0.5$, comparing the running time. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mpUUZQmbDx", "reviewer": "Reviewer_ooE5", "summary": "The authors perform a theoretical study of the branched optimal transport (BOT) in the plane, and also suggest a heuristic optimization strategy for the problem. On the theoretical side, they give a geometric construction algorithm for plane BOT solutions, argue for degree 3 branching of the optimal networks via a generalized argument of Bernot et al., and generalize this statement to 2D Riemannian manifolds embedded in $R^3$. \n\nOn the numerics and optimization side, their algorithm has two subalgorithms: one aimed at optimization of branching points given a tree topology, and another aimed at optimizing the tree topology. The first is inspired and drawn from a method of Smith for finding Steiner trees, while the second follows an informed heuristic based on node-edge distance to delete random edges and replace them with improved topologies. The method is tested on small numbers of terminals and is shown to achieve optimality quickly in many instances compared to the brute-force approach.", "questions": "1. Do you have any specific machine learning applications in mind for this problem? Many examples are given or suggested for OT with convex costs, but not for OT with concave costs. In particular, I imagine the plane restriction might be rather limiting, since most data in ML is high-dimensional.\n2. Do you have more detailed information on runtime that could be placed in the main text and/or summarized there? I think many researchers looking to apply your method would be interested to have them there.\n3. Do you have any insights on whether the techniques or heuristics would be valid for the problem in higher dimensions?\n4. Why didn't you compare to the algorithm of Oudet and Santambrogio (A Modica-Mortola approximation for\nbranched transport and applications)?", "limitations": "The authors have acknowledged the limitations of their method, which mainly center around limited scope, but have not motivated why this limited scope is still interesting.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The theoretical arguments are rather extensive and seem valid, as far as I have checked them.\n- The problem tackled is an interesting one, from a theoretical perspective, and does not seem to be extensively studied. \n- The result on limited degree of branching points is a nice, easy to understand, and impactful result.\n\nWeaknesses: \n- The paper does not cover or recommend any concrete ML applications of the plane BOT problem.\n- Nearly all of the theoretical arguments and constructions, as well as the optimization procedure for fixed topology are generalizations of ideas presented in other approaches.\n- The result on generalization to 2D embedded surfaces seems relatively straightforward and not all that significant perhaps. Especially without algorithms adapted to that scenario, or example uses.\n- The exposition is challenging to follow, as it generally provides brief glimpses into various theoretical constructions, and then directs the reader to extensive appendices.\n- The numerical section is rather brief, given the applied nature of NeurIPS. Only one simple experiment is referenced (though more are in the appendix.\n\nThis paper leaves me wandering if it would be better split into a theoretical and numerical investigation. The theoretical portion could be submitted to a different venue, while the numerical portion could be more extensively explored and detailed. As it stands, the paper is sort of an odd omnibus.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jQqo_E7N6go", "reviewer": "Reviewer_C23R", "summary": "The paper studies Branched Optimal Transport (BOT). The problem consists of finding the optimal topology, and achieving the optimal geometry of the BOT network of multiple sources and sinks, given the optimal topology. While it is known that the optimal topologies for such embeddings are trees, the authors make a further step by show that, in the optimal topology, every branching point has at most 3 neighbors. Given the optimal topology, this work also proposes a new geometric optimization strategy for the case of multiple sources, which is generalized from an approach in the literature.  The results also generalize to BOT on Riemannian manifolds. Finally, based on the developed results, they propose heuristic algorithms to solve the BOT problem.\n", "questions": "N.A.", "limitations": "As above. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "My main concern is that the paper's scope might not be much relevant to the ML community, while certain technical contribution can be interesting. The theoretical results can fit the mathematics community more for its combinatorial and geometrical nature, or fit the OR community for its relevance to routing and/or transportation systems. Yet, I cannot see how this paper can much benefit the ML community. Note that though OT is a simpler formulation than that considered in this work, it has applications in GAN vastly, domain adaptation, and color transfer, etc. so research aiming to solve OT competitively or study OT has been helpful. \nThe authors may consider well motivating the paper by some concrete applications in ML, whereby BOT is part of the problem formulation or at least conveys some idea/intuition. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eGSHJG5gccD", "reviewer": "Reviewer_CZsf", "summary": "The authors consider the branched optimal transport (BOT) problem with multiple sources. There is a finite number of sources with supplies and sinks (terminals) with demands located at fixed positions. We optimize the transportation between sinks and demands with respect to a directed edge-weighted graph and positions of nodes. The edges interconnect the terminals with the help of additional nodes (branching points). The edge direction indicates the direction of mass flow. The edge weight specifies the absolute flows.\n\nFirst, the authors investigate the topology and geometry of BOT solutions. They prove sufficient and necessary conditions for a BOT solution to be optimal for a chosen topology (lemma 2.1). Then the authors proposed a geometric approach to optimize BOT solutions, a generalization of the previously proposed approach, developed for BOT problems with a single source.\n\nSecond, the authors consider conditions under which coupled branching points (BPs) are not optimal, which can be used to improve the transportation cost of a BOT solution. In particular, they proved that topology could be improved if its relatively optimal solution (ROS) contains coupled BPs. \n\nThird, they consider the case of two-dimensional Riemannian manifolds embedded into 3-dimensional Euclidean space. The authors proved a necessary condition for a ROS.\n\nFinally, they propose heuristics and numerical optimization, which contains an effective algorithm for geometry optimization, followed by a heuristic for topology optimization. The authors claim that the paper is the first to propose heuristics for multiple sources, which do not require user supervision.", "questions": "- The paper (if we also consider the results in the Appendix) is very long. Still, I think it could be interesting to see some corner cases:\n1) The authors mentioned methods from [26, 28] for the single source case. What is about comparing their performance to the proposed approach? Also, a comparison with the method from [21] can be made.\n2) For alpha = 1, we get an OT problem. What is about comparing the proposed approach to some standard OT solvers?\n3) Performance of the simulated annealing procedure significantly depends on how the probability of sampling a particular edge is defined and how the normalizing factor d_min is defined. Any empirical results on how this influences the performance?\n\n- Description of Algorithm 2 in Appendix: step 7 is missing?\n\n- On the one hand, the theoretical part of the paper is well written; on the other hand, I think some additional structuring of the text is needed. The paper proposes a novel algorithm. Different parts of the algorithm are scattered across the main text, while their detailed description is in the Appendix. I would propose to include some description of the main steps of the algorithm and references to the corresponding sections of the main text and the Appendix where the detailed description is provided.\n\n- Figure 3: it seems that in Figure 3(c) a_0 is missing\n\n- Section E.1.4 about the “numerical” proof for the remaining parameter space. Any comments on specific technical difficulties why it is impossible to provide analytical proof?\n\n- Any fundamental qualitative explanation of the magic scaling n^{1.4} in line 1089 in the Appendix? What is the reason for such scaling?\n\n- Any experiments for the Riemannian case?", "limitations": "The paper does not have any negative societal impact. It can have even positive societal impact since some resource allocation problems can be solved using the proposed approach, which is essential from ESG perspective.\n\nI think that the limitations of the proposed approach are also adequately addressed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The authors consider a problem statement of a branched optimal transport (BOT) problem with multiple sources. Although the problem statement is purely theoretical, many real-world problems can be formulated in this way. So I consider the topic of the paper important.\n- The results seem novel: the paper contains many new results about the properties of ROS for the BOT problem and new algorithms.\n- The text of the paper is clearly written.\n\nWeaknesses\n- The paper is a bit theoretical. In particular, the authors did not consider solutions to any applied problems based on the proposed methods.\n- I would propose to add some additional ablation studies; see comments below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept